Родился 20 апреля 1922 года в деревне Варваровка, ныне Медынского района Калужской области, в семье крестьянина. С 1930 жил в городе Коломне ( Московская область ). Образование среднее. С 1940 года в Красной Армии. Окончил Качинскую военную авиационную школу лётчиков.

С июня 1941 года на фронтах Великой Отечественной войны. По сентябрь 1941 года служил в составе 16-го истребительного авиаполка, летал на МиГ-3. По январь 1942 года - 565-м авиаполку. По сентябрь 1942 года - в 487-м авиаполку. Затем, по декабрь 1943 года - в 910-м авиаполку, где летал уже на "Яках".

К маю 1943 года лётчик 910-го истребительного авиационного полка ( 101-я истребительная авиационная дивизия, Войска ПВО страны ) лейтенант А. А. Елдышев совершил 272 боевых вылета, в 17 воздушных боях сбил лично 11 и в составе группы 7 самолётов противника.

9 октября 1943 года за мужество и воинскую доблесть, проявленные в боях с врагами, удостоен звания Героя Советского Союза.

17 декабря 1943 года погиб в бою под Киевом. Всего выполнил около 300 боевых вылетов. В 25 воздушных боях сбил 15 вражеских самолётов лично и 7 в группе с товарищами.

Награждён орденами Ленина, Красного Знамени. Похоронен в селе Ивановка Белоцерковского района Киевской области.