Окончив 7 классов и строительный техникум, Андрей Федотов стал работать на Нижнесергинском металлургическом заводе, пока не призвали его в 1935 году в Красную Армию. В 1938 году закончил Оренбургское военное авиационное училище лётчиков и служил в истребительном авиационном полку.

Боевое крещение старший лейтенант А. А. Федотов получил во время "Зимней войны" с Финляндией. За воинское мастерство и отвагу он был удостоен первой награды - ордена Красного Знамени.

С началом Великой Отечественной войны - вновь на фронте, сражался в составе 49-го Краснознамённого истребительного авиаполка. Федотов познал горечь поражений в первые дни Отечественной войны и радость первых побед под Москвой. Потом сражался под Орлом. Долгое время он был штурманом полка, а затем его командиром. Добрый наставник молодых лётчиков, бесстрашный и суровый в воздушных боях и отзывчивый на земле. Таким знал его личный состав части.

Ему довелось сражаться почти на всех серийных отечественных истребителях своего времени: на И-153, И-16, МиГ-3, Як-1, Як-7, Ла-5. Уже первой военной осенью за несколько сбитых вражеских самолётов А. А. Федотов был награждён орденом Ленина.

С особенной силой его воинское дарование раскрылось после перевооружения полка в декабре 1942 года на новые Ла-5, который он освоил одним из первых. 16 декабря Федотов провёл воздушный бой на Ла-5 против новейшего немецкого истребителя FW-190. Исход поединка оказался в пользу советского лётчика и нового истребителя конструкции Семёна Лавочкина.

17 декабря полк выполнял весьма ответственную задачу - прикрытие группы бомбардировщиков Пе-2, атаковавших аэродром Смоленск, находившийся в глубоком тылу противника. Девятка Ла-5 под командованием дважды орденоносца капитана А. А. Федотова надёжно прикрыли Пе-2. Выполнив задачу, все бомбардировщики возвратились на свой аэродром. Истребители также потерь не имели.

Под Новый год, 29 декабря, в нескольких вылетах он сбил сразу 3 самолёта противника. Изощрённый в воздушном бою мастер высшего воздушного пилотажа, решительный командир, доброжелательный и приветливый человек, он был живым кумиром молодых лётчиков. Один из его питомцев, легендарный Алексей Маресьев вспоминал о командире:

"Я участвовал в боях в рядах 63-го Гвардейского истребительного полка, которым командовал Герой Советского Союза Гвардии майор Андрей Андреевич Федотов. Это был необыкновенно храбрый лётчик и мудрый командир. Андрей Андреевич всегда оставался человеком большой души и редкой доброты".

К марту 1943 года штурман 63-го Гвардейского истребительного авиационного полка  ( 3-я Гвардейская истребительная авиационная дивизии генерала В. П. Ухова )  Гвардии майор А. А. Федотов совершил 160 боевых вылетов, в воздушных схватках сбил 15 самолётов противника.

Особенно напряжёнными оказалась для Гвардейцев первая неделя весны. Так, 5 марта группа из 6 Ла-5, возглавляемая Гвардии майором А. А. Федотовым, встретила 6 пикировщиков Ju-87 шедших под прикрытием 4 Ме-109 и атаковала их. Метким огнём майора А. А. Федотова, старшего лейтенанта Г. И. Запорожченко и лейтенанта П. А. Гражданинова было сбито 3 "Юнкерса".

Не успели "Лавочкины" после боя собраться, как появилась вторая группа самолётов противника: 8 бомбардировщиков и 8 истребителей. Федотова не испугало явное численное превосходство врага. Он принял решение парой лейтенанта Гражданинова связать боем вражеских истребителей сопровождения, а своё звено повёл в атаку на пикировщиков.

И в этом бою атака Федотова оказалась роковой для врага: запылал один Ju-87. Завязался ожесточённый бой. Наши лётчики не давали бомбардировщикам врага прицельно сбрасывать бомбы. Не выдержав натиска, немцы сбросили бомбовой груз куда попало, поспешно развернулись и ушли на свою территорию. Но победа досталась дорогой ценой - лейтенант Павел Гражданинов и его ведомый сержант Александр Давыдов из этого воздушного боя не вернулись...

За образцовое выполнение боевых заданий командования, мужество, отвагу и геройство, проявленные в борьбе с немецко - фашистскими захватчиками, Указом Президиума Верховного Совета СССР от 1 мая 1943 года Гвардии майор Федотов Андрей Андреевич удостоен звания Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда"  ( № 967 ).

Словно отвечая на эту высокую награду Родины, в последующих боях он сбил ещё 5 вражеских самолётов.

12 июля 1943 года части Красной Армии Брянского фронта перешли в контрнаступление в районе Залегощ Новосиль - Мценск в общем направлении на город Орёл. Прорвав сильно укреплённую оборону противника и преодолевая исключительно упорное сопротивление врага, наши доблестные пехотинцы, танкисты и артиллеристы неудержимо рвались вперёд. Немцы пытались введением большой массы танков, артиллерии, самоходных пушек, а особенно авиации остановить наши войска. Но всё это было тщетно.

Наши лётчики - истребители надёжно прикрыли с воздуха боевые порядки наступающих войск. О большой напряжённости воздушных боёв можно судить по следующим фактам: в течение первого дня наступления на участке патрулирования 63-го ГвИАП было зафиксировано 150 самолёто - вылетов противника. В многочисленных воздушных боях со стороны немцев участвовало 90 самолётов, с нашей стороны - 57 самолётов. Зачастую бои происходили со значительным численным превосходством противника. Но наши лётчики ни одного раза не уступили в бою. Они с честью выполняли свою Гвардейскую клятву и воинский долг. В первый день наступления полком было сбито 11 самолётов противника: 9 истребителей и 2 бомбардировщика. Особенно отличился Гвардии майор А. А. Федотов, который своими исключительно умелыми действиями и особенно руководством ведомых им групп, обеспечивал победу.

В один из дней Федотов повёл на очередное боевое задание восьмёрку "Лавочкиных". Наши истребители появились вовремя - большая группа немецких бомбардировщиков подходила к лощине, где располагался штаб танкового соединения генерала П. С. Рыбалко. Федотов увеличил скорость и сверху слева устремился на вражеского ведущего. Огненная струя метнулась к кабине бомбардировщика, и тот загорелся. Увлечённые примером командира, смело действовали и молодые лётчики. В небе засверкали огненные трассы. Рухнул на землю ещё один "Хейнкель-111". Но и наш истребитель загорелся. Лётчик успел выброситься с парашютом. Группа Федотова возвращалась на аэродром пусть с небольшой, но всё - таки победой.

20 июля группа из 10 истребителей Ла-5 под командованием Героя Советского Союза Гвардии майора А. А. Федотова, прикрывая войска 3-й и 63-й армии, встретила 20 бомбардировщиков Ju-87 под прикрытием 24 истребителей FW-190. Федотов, твёрдо помня приказ не допускать бомбовых ударов по наземным целям, не задумываясь, повёл товарищей на врага. Бой был исключительно напряжённым. Противник потерял 13 самолётов, один из которых уничтожил ведущий нашей группы. В этом бою понесла потери и наша группа: на аэродром не вернулся лётчик В. П. Едунов.

15 декабря 1943 года к нашему переднему краю шли 3 девятки "Юнкерсов". По боевой тревоге командир 63-го Гвардейского истребительного авиационного полка Гвардии подполковник А. А. Федотов сам повёл дежурную эскадрилью наперехват. Четвёрку послал вверх для прикрытия, две пары оставил против бомбардировщиков. Федотов понял, что наши истребители не успеют набрать высоту, а потому атаковать бомбардировщики решил с ходу, в лоб вражеским самолётам, и, пока не подойдут остальные лётчики полка, драться малыми силами.

Командир полка увидел, как "Юнкерсы" ровными косяками подошли к переднему краю, намереваясь бомбить наши окопы. Федотов нацелил свой "Лавочкин" на головной бомбардировщик. Он уже различал заклёпки бомболюка, нажал на гашетку, и огненные струи вонзились в фюзеляж "Юнкерса", из него вырвалось пламя. Но в тот же миг Федотов неожиданно был атакован четвёркой Ме-109 и погиб. С яростью ударили его ведомые по вражеским бомбардировщикам, не позволив им сбросить бомбы на наши наземные войска.

К тому времени он совершил более 200 боевых вылетов, доведя число сбитых вражеских самолётов до 22  ( 21 самолёт сбил лично и 1 в группе ).

Похоронен Герой у села Вышедки Невельского района Псковской области. Его именем названа улица в городе Нижние Серги. На фасаде дома, в котором он жил, и на здании школы, где учился, установлены мемориальные доски.

Приказом Министра обороны СССР за № 162 от 18 июня 1968 года Герой Советского Союза Гвардии подполковник Федотов Андрей Андреевич навечно зачислен в списки 1-й авиационной эскадрильи 470-го Гвардейского Виленского ордена Кутузова истребительного авиационного полка ПВО  ( так после войны стал именоваться 63-й Гвардейский ИАП ).

Список всех известных побед Гвардии подполковника А. А. Федотова:
( Из книги М. Ю. Быкова - "Победы сталинских соколов".  Издательство "ЯУЗА - ЭКСМО", 2008 год. )