Его восемнадцати летним парнем в 1942 году призвали в армию. Он попал в Воздушно-десантные войска. Не раз прыгал с парашютом в ночною бездну, а потом состоялся и первый бой. Его десант высадили на правый берег Днепра под Киевом. Тогда полк лишился многих десантников, но Алексей остался жив. В том бою под Днепром 2438 солдат и офицеров были удостоены высокого звания Героя Советского Союза. Молоденький солдат-десантник уже в первой бою стал причастен к народному подвигу на Днепре. А затем последовали другие десанты, в результате которых ему было присвоено звание сержант и уже тогда он возглавил пулеметное отделение и в составе стрелкового полка пересёк Карпаты и с боями прошел пол-Европы.
В одном из боев Алексея вместе с напарником из Удмуртии накрыло взрывной волной, в результате которой напарник погиб. Выбравшись из-под земли, ему пришлось догонять роту, т.к. она ушла вперёд. За проявленные героизм и мужество сержанту Алексею Фёдорову лично маршал Фёдор Толбухин вручил орден III степени.
Затем новое задание - марш-бросок в Чехословакию, чтобы отсечь группировку противника. И когда в Берлине над рейхстагом уже развевался флаг Победы, Алексей продолжал вести бой под Прагой.
Много орденов и медалей на его груди: за взятие Будапешта, Вены и праги, орден Отечественной войны II степени, медаль "За отвагу", и "За победу над Германией".