В Красной Армии с 1938г.

Вероятно, окончил ШМАС (школа младших авиаспециалистов) или курсы воздушных стрелков-радистов.

К августу 1942г. в составе 39 ближне-бомбардировочного авиаполка. Полк находился в г.Энгельс, осваивая самолеты Пе-2.

На фронте с 16 декабря 1942г. в составе 202 бомбардировочной авиадивизии 3 смешанного авиакорпуса. Базировался на аэродроме Нижняя Каменка. Вел боевую работу на Среднем Дону.

16 декабря экипажи полка атаковали войска противника в районах Гадючье и Филоново.

Экипажи полка уничтожали войска противника и вели воздушную разведку.

В январе 1943г. полк базировался на аэродроме Калачевский совхоз. Участвовал в освобождении Донбасса.

17 января полк в составе 10 самолетов Пе-2 перебазировался на аэродром Березняги.

25 января- на Гармашевку. 

04 февраля- на Новодеркул.

07 и 08 февраля экипаж Алексея Андреевича выполнил задание по разведке, установив движение войск противника в район Донбасса.

Сержант Холодов, совершивший 13 успешных боевых вылетов, был представлен к ордену Красной Звезды, приказом от 14 февраля 1943г. награжден медалью «За отвагу».

09 марта 1943г. группа из 7 самолетов Пе-2 под прикрытием 8 истребителей Ла-5 с высоты 900м. бомбардировала войска противника в д.Терновая. Были атакованы 8 истребителями Ме-109. 6 «мессеров» завязали бой с нашими истребителями прикрытия, а два незаметно зашли сзади-снизу к группе «пешек» и атаковали. В воздушном бою были подбиты два самолета Пе-2. С задания не вернулся экипаж: пилот младший лейтенант Назарьев Петр Антонович, стрелок-бомбардир младший лейтенант Сечкин Иван Прохорович, стрелок-радист старший сержант Холодов Алексей Андреевич.