Алексей Алелюхин родился 30 марта 1920 года в селе Кесова Гора Тверской губернии в семье рабочего. Закончив начальную школу, работал на Московской фабрике канцелярских товаров и одновременно учился в планёрной школе.
В Красной Армии с 1938 года. Призван Мытищинским РВК Московской обл. Окончил военную авиационную школу имени В. П. Чкалова в 1939 году.
В 1941 году вступил в ВКП(б)
Алелюхин принимал участие в Великой Отечественной войне с первого дня войны в Одесском военном округе на самолёте И-16. Здесь начал сбивать самолёты противника и получил первую награду — орден Красного Знамени. В одном из боёв был ранен. Осенью 1941 года 69-й ИАП, в котором служил Алексей Алелюхин, был перевооружён с И-16 на новые ЛаГГ-3. На этой машине Алелюхин одержал ряд побед.
Во время Сталинградской битвы под Калачом сбил четыре бомбардировщика противника, а под Котельниковом — два «юнкерса» и один «мессершмитт». За данные победы Алелюхин был награждён Орденами Ленина и Красного Знамени.
Во время Мелитопольской операции в одном бою девятка под командованием Алелюхина смело атаковала 50 бомбардировщиков противника, шедших под прикрытием истребителей. Советские лётчики, сбив ведущие самолёты, расстроили боевой порядок самолётов противника и посеяли панику среди фашистских лётчиков. Немецкие бомбардировщики сбросили бомбовый груз на позиции своих войск.
В феврале 1943 года к востоку от Ростова-на-Дону Алелюхин встретил в небе немецкого аса Баркхорна (второго по результативности летчика Люфтваффе). Бой продолжался 23 минуты, но не дал результатов. Баркхорн вышел из боя полностью обессиленным и полным восхищения мастерством противника.
Звания Героя Советского Союза командир эскадрильи 9-го гвардейского истребительного авиационного полка (6-я гвардейская истребительная авиационная дивизия, 8-я воздушная армия, Южный фронт) гвардии капитан Алелюхин был удостоен 24 августа 1943 года за 265 боевых вылетов и участие в 65 воздушных боях, в которых лично сбил 11 самолётов противника и 6 в группе.
Второй медалью «Золотая Звезда» удостоен 1 ноября 1943 года за 410 боевых вылетов и участие в 114 воздушных боях, в которых лично сбил 26 самолётов врага и за образцовое выполнение боевых заданий командования при освобождении Донбасса.
К концу войны Алексей Алелюхин воевал на именном — истребителе Ла-7 с надписью на борту «Алексею Алелюхину от коллектива треста N: 41 НКАП». Последний бой провёл в небе Германии, сбив Fw-190 в воздушном бою.
За время войны Алелюхин совершил 601 боевой вылет, проведя 258 воздушных боёв, лично уничтожил 40 вражеских самолётов и ещё 17 — в составе группы.
Работал на командных должностях. В 1948 году закончил Военную академию имени М. В. Фрунзе, в 1954 году — Военную академию Генштаба.
В 1985 году генерал-майор авиации Алелюхин ушёл в отставку.
Умер 29 октября 1990 года в Москве. Похоронен на Новодевичьем кладбище.
Бронзовый бюст установлен на родине. Его имя носит улица во Львове.