Родился в семье потомственного дворянина Орловской губернии. Получил образование в престижном учебном заведении — Императорском Александровском (бывшем Царскосельском) лицее. В 1878 начал службу в Государственной канцелярии, а в следующем году стал кандидатом на судебные должности при прокуроре Саратовского окружного суда. Участвовал в ревизии, проводимой сенатором И. И. Шамшиным в Самарской губернии. С 1884 товарищ прокурора Саратовского окружного суда, а с 1886 — редактор департамента Министерства юстиции. Занимал также должности чиновника особых поручений, управляющего законодательным отделением и юрисконсульта.
В 1894 перешел на службу в Министерство внутренних дел, где занял пост правителя канцелярии, а позднее директора хозяйственного департамента. В 1901 вернулся в Министерство юстиции на должность директора 1-го департамента.
26 января 1905 А. А. Хвостов становится товарищем министра юстиции, а в конце года — сенатором. В Правительствующем сенате служил шесть лет. 1 января 1912 назначен членом Государственного совета. 6 июля 1915 ему поручается управление Министерством юстиции (с оставлением членом Государственного совета и сенатором), а 30 сентября того же года Александр Алексеевич утверждается в должности министра юстиции и генерал-прокурора.
7 июля 1916 Хвостов был освобожден от занимаемой должности и неожиданно для себя назначен министром внутренних дел. Однако через два месяца оставил и этот пост, сохранив за собой только должности сенатора и члена Государственного совета. 1 января 1917 произведен в действительные тайные советники. Награжден многими орденами, включая орден Св. Александра Невского.
После Февральской революции 1917 Хвостов проживал в своем имении в Елецком уезде Орловской губернии. Он был допрошен в Чрезвычайной следственной комиссии, но обвинение ему не предъявлялось. После Октябрьской революции А. А. Хвостов счастливо избежал участи многих царских сановников, расстрелянных по приговорам революционных трибуналов. Он проживал с семьей в г. Ельце, занимался хозяйством. По воспоминаниям дочери, писал мемуары.
А. А. Хвостов скончался 23 ноября 1922.