Указом Президиума Верховного Совета СССР от 1 ноября 1943 г. гвардии капитан А.В. Алелюхин был награжден второй медалью «Золотая Звезда».

А.В. Алелюхин не раз попадал в критические ситуации, но всегда находил из них выход. 25 апреля 1944 г. во время воздушной схватки в районе Севастополя Алелюхин сошелся в лобовой атаке с истребителем FW-190. Вражеский снаряд пробил 38-миллиметровое лобовое бронестекло кабины и ранил Алелюхина в лицо, шею и плечо. Несмотря на это, Алексей Васильевич остался в строю, и вскоре повел свою эскадрилью на боевое задание.

Еще один случай произошел 5 мая 1944 г. «При подходе к переднему краю, – писал в донесении заместитель командира полка по политической части гвардии подполковник Н.А. Верховен, участвовавший в этом боевом полете, – в районе Макензиевых гор были атакованы ФВ-190. В результате атаки моя пара оказалась в угрожающем положении. Тогда гвардии майор Алелюхин, который вел вторую четверку, сделал резкий разворот влево, отбивая атаки истребителей противника от меня. У самолета Алелюхина были повреждены рули высоты, и он стал штопорить. Летчик выпрыгнул с парашютом и приземлился в расположение 31-й гвардейской дивизии».

В конце войны Алелюхин летал уже на именной машине – истребителе Ла-7 с надписью на борту: «Алексею Алелюхину от коллектива треста № 41 НКАП». Один из последних боев, в которых участвовал Алексей Васильевич, произошел 13 апреля 1945 г. над Пиллау (ныне Балтийск). Алелюхин, будучи ведущим шестерки самолетов Ла-7, повел их на блокирование вражеских аэродромов Нойендорф и Нойгиф. После десяти минут патрулирования в районе цели на высоте 3000 метров капитан Б.В. Масленников заметил шесть FW-190, которые прикрывали порт Пиллау. Алелюхин принял решение дать бой противнику, о чем по радио сообщил четверке Масленникова. В результате атаки четырьмя Ла-7 Масленников под прикрытием пары Алелюхина сверху и сзади сбил один «фоккер». Оставшиеся три вражеских самолета со снижением стали уходить к аэродрому Грос-Хубаникен. Имея преимущество в высоте и скорости, Алелюхин с ведомым И.Д. Белокудренко начали преследовать противника. Подойдя на близкую дистанцию, Алелюхин приказал ведомому открыть огонь, и Белокудренко с короткой дистанции сбил еще один FW-190.

15 ноября 1941 г. войска группы армий «Центр» возобновили наступление на Москву. В полосе Западного фронта соединения 3-я танковой группы нанесли удар по 30-й армии, а на следующий день в наступление против 16-й армии перешла 4-я танковая группа. В составе 16-й армии наиболее боеспособной была 78-я стрелковая дивизия полковника А.П. Белобородова, прибывшая из Сибири. Она насчитывала 14 тыс. бойцов и командиров, 23 легких танка, 66 орудий, 59 минометов, 441 автомашину и 3400 лошадей. Части дивизии оказали противнику ожесточенное сопротивление. «Завязываются жестокие бои, – писал в своем отчете командующий 4-й немецкой танковой группой генерал-полковник Э. Хепнер[8]. – Особенно упорные в полосе дивизии “Рейх”. Ей противостоит 78-я сибирская стрелковая дивизия, которая не оставляет без боя ни одной деревни, ни одной рощи. Потери наступающих очень велики. Рядами встают кресты над могилами танкистов, пехотинцев – солдат войск СС».

А.П. Белобородов стал героем очерка писателя Александра Бека, который, пробыв сутки рядом с ним, изложил по часам, а то и поминутно, один день работы комдива в бою. «Эти дни потрясли меня, – пишет Бек. – Много раз приходилось слышать рассказы участников войны, кое-что видел сам, но не подозревал, что люди могут драться так, как дрались красноармейцы 78-й».