Начал войну в октябре 1941 года курсантом в батальоне связи, затем учёба в училище - Первом Гвардейском миномётном артиллерийском Краснознамённом имени Красина. После окончания офицерского училища, получив звание лейтенанта, Алексей, как и его товарищи, ждал направления на фронт, а их отправили в Москву в первую учебную гвардейскую минометную артиллерийскую бригаду, где готовили младший командный состав для "Катюш".

Первое боевое крещение получил молодой боец Алеша Малоштанов под Сталинградом. До 2 февраля 1943 года был командиром взвода «Катюш» в 94-м Гвардейском Краснознамённом ордене Суворова, Кутузова, Богдана Хмельницкого и Александра Невского полку воевал он командиром взвода "Катюш".

Война не давала передышки. Орлово-Курская битва в составе первого Белорусского фронта, потом бои за освобождение Белоруссии, освобождение Варшавы, форсирование реки Одер. Командир батареи "Катюша" Алексей Малоштанов вместе со своими боевыми товарищами в январе 1945 года принял участие в прорыве обороны немцев на Зеловских высотах, потом выход на окраины Берлина, битва за Берлин...

"Шла перегруппировка войск с целью поддержки наступления пехоты и танков. В конце апреля-начале мая Берлин пал. Артиллерия первого Белорусского фронта сосредоточилась в районе Берлина. Слово "победа" уже витало в воздухе. Всем было ясно, что скоро конец этой страшной войне. Даже воздух пронизан тем особым запахом, который чувствуешь только весной...В тот весенний день, вернее в ночь на 9 мая 1945 года, - рассказывал Алексей Прокофьевич Малоштанов, - я был дежурным по полку. Вдруг слышу выстрелы, крики, шум. "ПО-БЕ-ДА!!!" Сотни голосов слились в один мощный, зычный, с перекатами, похожий на отдаленный гром, голос. Победа! Радость людей была беспредельна. У каждого из нас, ветеранов, свой особый отсчет времени и счет к войне, свои воспоминания."

Участвовал в операции «Уран», в Орлово- Курской битве, в освобождении Белоруссии , освобождении Варшавы, форсировании реки Одер, участие в прорыве обороны немцев на Зеловских высотах, битва за Берлин.