Алексей Толстой родился 14 (26) июня 1840 года. Православного вероисповедания. Происходил из дворянского рода ТолстыхТверской губернии. Сын генерал-майора Владимира Андреевича Толстого (17991842) и Варвары Андреевны, урождённой Щербининой.
Образование получил в Императорском училище правоведения, по окончании которого 16 июня 1861 года поступил на военную службу унтер-офицером в Переяславский драгунский полк. С того же года Толстой в составе этого полка принимал участие в Кавказской войне вплоть до её окончания в 1864 году. 16 декабря 1862 года произведен в прапорщики, а в следующем 1863 году был награждён орденом Св. Георгия 4-й степени. 21 мая 1864 года в день окончательного завершения кавказской войны за боевые отличия в боях с горцами был произведён в офицерский чин поручика.
26 июня 1866 года произведен в штабс-капитаны. 24 декабря того же года он был назначен на должность адъютанта главнокомандующего Кавказской армией великого князя Михаила Николаевича. 30 августа 1868 года произведён в поручики гвардейской кавалерии в лейб-гвардии Гусарский Его Величества полк с оставлением в занимаемой им должности. 30 августа 1871 года произведен в штабс-ротмистры, и с 10 декабря того же года назначен командиром конвоя главнокомандующего Кавказской армией. 30 августа 1874 года произведен в ротмистры, а 27 мая 1877 года в полковники.
В Русско-турецкую войну 18771878 годов продолжал состоять адъютантом при главнокомандующем Кавказской. С 12 по 13 июня 1877 года в составе наспех сформированного Чингильского отряда участвовал в неудачном марш-броске на Баязет, для освобождения осаждённого в его цитадели русского гарнизона. С 10 октября 1877 по 1 марта 1878 годы командовал 2-й бригадой 2-й кавалерийской дивизии. 23 октября 1877 года получил лёгкое ранение при взятии Хасан-кале.
С 9 января 1889 года Толстой был произведён в генерал-майоры, а 6 декабря 1899 года в генерал-лейтенанты. Умер в 1907 году (исключён из списков умершим 23.09.1907).