Родился 6 июня 1962 года в Махачкале. Проходил обучение в Витебском авиационном центре ДОСААФ, затем в Саратовском высшем военном авиационном училище лётчиков. С 1985 года служил на различных лётных должностях в Ленинградском военном округе, с 1993 года — в Северо-Кавказском округе внутренних войск МВД России. С июля 1999 года участвовал в выполнении специального задания в составе временной оперативной группировки войск на территории Северного Кавказа.

11 августа 1999 года вместе с экипажем осуществлял доставку руководящего состава группировки, следующего в вертолёте Ми-8 по маршруту Махачкала – Агвали. В 15.01 вертолет, пилотируемый экипажем, который возглавлял майор Андрей Орлов, выполнил взлёт и взял курс на Агвали.

На борту вертолёта находились начальник авиационного управления Главкомата внутренних войск генерал-лейтенант Виктор Якунов, начальник разведуправления генерал-лейтенант Виктор Кузнецов и заместитель начальника Главного организационно-инспекторского управления МВД России генерал-майор внутренней службы Виктор Ракитин. Кроме них на борту были два офицера ФАПСИ РФ со спецаппаратурой и два солдата сопровождения из отряда спецназа «Росич».

В 15.43 при заходе на посадку у населённого пункта Ботлих Республики Дагестан вертолёт был подбит управляемой ракетой. Машина загорелась. Командир экипажа майор Орлов был тяжело контужен, горел, но пытался ещё отдавать какие-то распоряжения, организовать эвакуацию пассажиров, которые успели, помогая друг другу, покинуть горящий борт и отойти на безопасное расстояние. А через несколько мгновений ещё одна вражеская ракета попала в горящий Ми-8.

Майор Андрей Орлов получил тяжёлые ожоги. 15 августа 1999 года он скончался от полученных ран.

Указом Президента Российской Федерации от 26 августа 1999 года за мужество и самоотверженные действия, проявленные при выполнении специального задания, майору Орлову Андрею Борисовичу присвоено звание Героя Российской Федерации (посмертно).

Похоронен в Ростове-на-Дону.