– Когда сгоряча расстреляли весь боекомплект, – вспоминал Алексей Васильевич, – ведущий собрал девятку и подал сигнал возвращаться домой. Во время штурмовки чувствовал себя хорошо, даже в раж вошел, а когда домой пришли, заметил, как коленки дрожат от волнения. Ну и шуму было, когда приземлились: поздравляли друг друга с боевым крещением, чуть не обнимались. Потом такие полеты, конечно, стали привычными, и я уже не воспринимал их как нечто необычное.
В небе над Одессой уже на третий день войны Алелюхин на истребителе И-16 в составе звена сбил над аэродромом вражеский бомбардировщик Не-111. К августу 1941 года Алелюхин совершил 83 боевых вылета.
Осенью 1941 г. летный состав 69-го истребительного авиационного полка пересел на новые истребители ЛаГГ-3. На этой машине Алелюхин отважно сражался в небе Сталинграда, под Мелитополем, на реке Молочная. Каждый боевой вылет был сопряжен с огромным риском. Не всегда все проходило гладко, как по заранее отработанному сценарию. В одном из боев вражеский снаряд пробил кабину истребителя Алелюхина, и несколько осколков впилось ему в ногу. Истекая кровью, он дотянул свой самолет до аэродрома. А когда подлечился, снова начал летать на боевые задания.
– А вы испытываете чувство страха при встрече с превосходящими силами врага? – спросил Алелюхина корреспондент одной из газет.
– Так же, наверное, как и все, испытываю, – ответил Алексей Васильевич. – Но еще больше я боюсь того, что вдруг не собью врага и он уйдет, чтобы снова прийти сюда убивать наших людей. И это чувство настолько сильное и требовательное, что заглушает все другие, и я, подчиняясь ему, иду в бой, чтобы не враг меня, а я его сбил.
Сослуживцы Алелюхина вспоминали, что он был человеком удивительного хладнокровия. Крепко сбитый, словно отлит из железа, он был по-детски смешлив и добродушен. Но в боевой обстановке это добродушие моментально улетучивалось и перед вами представал решительный и энергичный воздушный ас. Журналист И.Я. Бражнин (Пейсин) в своей книге «В Великой Отечественной: сборник военных очерков» следующим образом характеризует Алексея Васильевича, с которым познакомился 1 марта 1943 г.:
7 марта 1942 г. приказом наркома обороны СССР 69-й истребительный авиационный полк за образцовое выполнение боевых задач и проявленные при этом мужество и героизм был переименован в 9-й гвардейский истребительный авиационный полк. В составе 268-й истребительной авиационной дивизии он принимал участие в Сталинградской стратегической наступательной операции. Алелюхин, пересевший к тому времени в кабину истребителя Як-1, в боях под Калачем сбил 4 вражеских бомбардировщика, а под Котельниковом и Зимовниками – два «юнкерса» и один «мессершмитт».