Алексей Перемытов происходил из Тамбовской губернии, из крестьянской семьи, был капитаном старой армии. Окончил ускоренные курсы Военной академии. В 1918 году добровольно пошел служить в Красную армию, став военспецом. Прошел всю Гражданскую войну. Занимал посты начальника оперативного управления штаба Западного фронта, начальника штаба 7-й армии, временно исполнял должность начальника штаба Южного фронта, служил начальником штаба Северо-Кавказского, Московского и Белорусского военных округов, преподавал в Военной академии имени Фрунзе.
В 1921-м году Перемытов награжден орденом Красного Знамени - "за исключительную доблесть и умелое руководительство операциею штурма крепости Кронштадт и боем по овладению гор[одом] Кронштадтом". В 1935 году ему присвоено воинское звание комдив.
Перемытов был приговорен к расстрелу Военной коллегией Верховного суда СССР по обвинению в шпионаже и участии в антисоветском военном заговоре 28 июля 1938 года и в тот же день расстрелян.
Список 138 лиц, подлежавших расстрелу, перед судом лично утвердили Иосиф Сталин и Вячеслав Молотов. Похоронен Перемытов на расстрельном полигоне "Коммунарка".
Реабилитирован в 1956 году за отсутствием состава преступления, однако потомкам было выдано свидетельство о смерти с ложным указанием на смерть Перемытова в 1942 году по естественным причинам.