Родился 25 марта 1920 года в городе Нижний Тагил (ныне административный центр Горнозаводского управленческого округа Свердловской области). Окончил среднюю школу № 30. С декабря 1938 года в рядах Красной Армии, призван Нижне-Тагильским ГВК. Окончил военную авиационную школу лётчиков. Служил в строевых частях ВВС. Участник похода Советских войск в Западную Белоруссию осенью 1939 года.

С 23 июня 1941 года младший лейтенант А. А. Толстов в действующей армии. Воевать начал в 184-м ИАП. Вёл боевую работу на Западном фронте (в составе 59-й ИАД, с 7 июля 1941 года - 11-й САД), летая на И-16. С 16 августа 1941 года сражался уже на Брянском фронте (в составе 11-й САД, с 13 февраля 1942 года - ВВС 3-й Армии). К 12 мая 1942 года 182-й ИАП был расформирован, а его личный состав направлен в другие полки.

С 12 мая 1942 года младший лейтенант А. А. Толстов воевал уже в 876-м ОСАП (в составе 3-й Армии, Брянского Фронта), продолжая летать на И-16. 12 марта 1943 года полк был расформирован, часть личного состава направлена на формирование Отдельной армейской авиационной эскадрильи связи 3-й Армии.

26 мая 1943 года лейтенант А. А. Толстов был направлен на должность старшего лётчика в 900-й ИАП, который находился в 17-м ОУТАП (15-й Воздушной армии, Брянского фронта), где проходил переучивание на новую технику. С 24 августа 1943 года приступил к боевой работе на Калининском фронте, который 20 октября 1943 года был переименован в 1-й Прибалтийский фронт (в составе 240-й ИАД, 3-й Воздушной армии), летая на Як-9Т.

К середине октября 1943 года старший лётчик 900-го истребительного авиационного полка (240-я истребительная авиационная дивизия, 3-я Воздушная армия, Калининский фронт фронт) старший лейтенант А. А. Толстов совершил около 150 боевых вылетов, в воздушных боях сбил лично 7 самолётов противника. В боях был ранен, лечился в госпитале, вернулся в часть 4 ноября 1943 года.

К тому времени полк боевой работы не вёл: находился в резерве 3-й Воздушной армии, занимался по плану учебно-боевой подготовки, проходил переформирование и пополнялся самолётами Як-9. 6 марта 1944 года старший лейтенант А. А. Толстов убыл в эвакуационный госпиталь № 5019 (видимо, по болезни). 24 ноября 1944 года был направлен в 354-й Отдельный авиационный полк связи (354-й ОАПС) при 1-й Воздушной армии. Из него был отправлен в 40-й ОУТАП, а затем в 1-й Отдельный санитарный авиационный полк (1-й ОСАНАП) при 1-й Воздушной армии.

После окончания войны продолжал служить в ВВС. С 6 февраля 1946 года старший лейтенант А. А. Толстов - в запасе (по состоянию здоровья). Вернулся на родину, работал на Нижнетагильском цементном заводе.

Награждён орденами: Красного Знамени (31.07.1942), Отечественной войны 1-й степени (2.09.1943); медалями.