– Забудь, что есть земля на свете, – говорил Алелюхин. – Будто ты родился в воздухе, будто сызмала тебя учили держаться за солнце и ходить в облаках, – так повторяю я себе каждый раз. И еще об одном должен помнить истребитель. Бой начинается не тогда, когда ты заметил противника. Сел в самолет, – значит, ты уже в бою. И соответственно веди себя в полете от первой до последней минуты. Тогда никто тебя не захватит врасплох.
К августу 1943 г. на счету Алелюхина уже было 265 боевых вылетов и участие в 65 воздушных боях, в которых он лично сбил 11 самолетов противника и 6 в группе. К этому времени действовал приказ № 0489 наркома обороны СССР И.В. Сталина от 17 июня 1942 г., согласно которому к званию Герой Советского Союза представлялись летчики-истребители, сбившие 10 истребителей или 5 бомбардировщиков противника. В соответствии с этим приказом Алелюхину 24 августа 1943 г. было присвоено высокое звание Героя Советского Союза.
В годы войны имя Алелюхина не раз упоминалось на страницах фронтовой печати и в специально выпущенных листовках. Например, в листовке политуправления Южного фронта отмечалось: «Алелюхин – мастер огня, мастер пилотажа, мастер маневра, он с одинаковым искусством владеет и машиной, и ее вооружением, и полем боя, и собой. И это всегда приносит отличные результаты. Где Алелюхин, там победа, там пылают и падают на землю фашистские машины».
Алелюхин нередко применял различные приемы ведения боя с целью ввести противника в заблуждение. Однажды, находясь в воздухе, он заметил две шестерки бомбардировщиков Ju-88. Они летели без прикрытия.
– В атаку! – приказал Алексей Васильевич по радио своим ведомым.
Дав полный газ, Алелюхин атаковал врага. Развернувшись в лучах солнца, истребители пристроились в хвост бомбардировщикам, которые, вероятно, приняли их за своих. Этим воспользовался Алелюхин. Он с короткой дистанции поймал один «юнкерс» точно в прицел, нажал на гашетку, и снаряды прошили его. Бомбардировщик взорвался и рухнул на землю. Неожиданно самолет Алексея Васильевича вздрогнул от взрывной волны. Впереди него загорелись и пошли к земле еще два бомбардировщика противника. Продолжая под прикрытием ведомого руководить боем, Алелюхин приказал четверке И.В. Тимофеенко атаковать следующую шестерку врага. Эта атака также принесла успех: были уничтожены еще два «юнкерса». Враг, потеряв пять самолетов, пришел в замешательство и, не сбросив бомбы, покинул район боя.
26 сентября 1943 г. войска Южного (с 20 октября 4-го Украинского) фронта приступили к проведению Мелитопольской наступательной операции с целью разгромить группировку немецкой 6-й армии, оборонявшую рубеж р. Молочная, освободить Северную Таврию и выйти к низовьям Днепра. В этой операции отличился 9-й гвардейский истребительный авиационный полк. 27 октября командир полка Герой Советского Союза подполковник А.А. Морозов подписал наградной лист на командира эскадрильи гвардии капитана Алелюхина, в котором говорилось: «При прорыве немецкой обороны в г. МЕЛИТОПОЛЕ его эскадрилья произвела 240 боевых самолето-вылетов, провела 93 воздушных боя и сбила 9 самолетов противника. Лично он произвел 34 боевых вылета, провел 11 воздушных боев, сбил 1 самолет противника. Умело руководя своими подчиненными, в составе 10 самолетов “Аэрокобра”, 1-го октября с. г., прикрывая свои войска в районе ВОРОШИЛОВКА, КОПАНИ, В. ТОКМАК, провел воздушный бой с 27-ю бомбардировщиками противника, под прикрытием МЕ-109. Благодаря мужеству и высокой дисциплине, его группа сбила 4 ХЕ-III и 1 МЕ-109, не дав возможности врагу сбросить бомбы на наши войска. Своей неутомимостью, храбростью в сочетании с разумной инициативой, он заражает своих подчиненных уничтожать врага, очищая воздух нашей священной Родины. За умелое руководство своими подчиненными, за личную храбрость и героизм, проявленные в борьбе с немецкими захватчиками, за 26 лично сбитых самолетов пр-ка, т. АЛЕЛЮХИН достоин высшей Правительственной награды – присвоения звания “ДВАЖДЫ ГЕРОЙ СОВЕТСКОГО СОЮЗА”».