Свой первый бой А.В. Алелюхин запомнил на всю жизнь. Эскадрилья, в которой он служил, вылетела на штурмовку вражеских позиций на Днестре. На высоте тысяча метров подошли к цели, развернулись всей девяткой и с пикирования стали бить по позициям противника из пулеметов.

– Когда сгоряча расстреляли весь боекомплект, – вспоминал Алексей Васильевич, – ведущий собрал девятку и подал сигнал возвращаться домой. Во время штурмовки чувствовал себя хорошо, даже в раж вошел, а когда домой пришли, заметил, как коленки дрожат от волнения. Ну и шуму было, когда приземлились: поздравляли друг друга с боевым крещением, чуть не обнимались. Потом такие полеты, конечно, стали привычными, и я уже не воспринимал их как нечто необычное.

В небе над Одессой уже на третий день войны Алелюхин на истребителе И-16 в составе звена сбил над аэродромом вражеский бомбардировщик Не-111. К августу 1941 года Алелюхин совершил 83 боевых вылета. «В воздушных боях с самолетами противника, – отмечал в наградном листе командир 69-го истребительного авиационного полка майор А.Н. Марьинский, – т. Алелюхин показал образцы мужества и геройства, поражая противника метким сильным огнем, отлично владея машиной, огромной силой воли к победе. За образцовое выполнение боевых заданий и проявив[7] при этом мужество и геройство, достоин правительственной награды ордена “Красного Знамени”». Этим орденом Алексей Васильевич был награжден 5 ноября 1941 г.

Осенью 1941 г. летный состав 69-го истребительного авиационного полка пересел на новые истребители ЛаГГ-3. На этой машине Алелюхин отважно сражался в небе Сталинграда, под Мелитополем, на реке Молочная. Каждый боевой вылет был сопряжен с огромным риском. Не всегда все проходило гладко, как по заранее отработанному сценарию. В одном из боев вражеский снаряд пробил кабину истребителя Алелюхина, и несколько осколков впилось ему в ногу. Истекая кровью, он дотянул свой самолет до аэродрома. А когда подлечился, снова начал летать на боевые задания.

– А вы испытываете чувство страха при встрече с превосходящими силами врага? – спросил Алелюхина корреспондент одной из газет.

– Так же, наверное, как и все, испытываю, – ответил Алексей Васильевич. – Но еще больше я боюсь того, что вдруг не собью врага и он уйдет, чтобы снова прийти сюда убивать наших людей. И это чувство настолько сильное и требовательное, что заглушает все другие, и я, подчиняясь ему, иду в бой, чтобы не враг меня, а я его сбил.

Сослуживцы Алелюхина вспоминали, что он был человеком удивительного хладнокровия. Крепко сбитый, словно отлит из железа, он был по-детски смешлив и добродушен. Но в боевой обстановке это добродушие моментально улетучивалось и перед вами представал решительный и энергичный воздушный ас. Журналист И.Я. Бражнин (Пейсин) в своей книге «В Великой Отечественной: сборник военных очерков» следующим образом характеризует Алексея Васильевича, с которым познакомился 1 марта 1943 г.: «Уже тогда 22-летний Алелюхин, сбивший лично 11 немцев и в группе 8, был признанным мастером воздушного боя – резкий, молниеносный, искусный и в пилотаже, и в ведении огня, и в боевой технике, выносливый, находчивый в трудные минуты боя, пилот с необыкновенной реакцией в управлении машиной и боевых движениях. К тому же он обладал способностью в самом процессе боя видеть вокруг себя решительно все – и своих ведомых, и самолеты противника, и все подходы к району боя, и сам бой на всем его пространстве».

7 марта 1942 г. приказом наркома обороны СССР 69-й истребительный авиационный полк за образцовое выполнение боевых задач и проявленные при этом мужество и героизм был переименован в 9-й гвардейский истребительный авиационный полк. В составе 268-й истребительной авиационной дивизии он принимал участие в Сталинградской стратегической наступательной операции. Алелюхин, пересевший к тому времени в кабину истребителя Як-1, в боях под Калачем сбил 4 вражеских бомбардировщика, а под Котельниковом и Зимовниками – два «юнкерса» и один «мессершмитт».