Tema isa oli erruläinud husaar ja maaomanik ning ema lastekirjanik. Kui Tolstoi ema oli kaks kuud rase, põgenes ta koos oma armukese Aleksei Apollonovitš Bostromiga kodust. Vastsündinud Aleksei kirjutas ta samuti Bostromi nimele. 13-aastaselt sai Aleksei Tolstoi teada, et ta bioloogiline isa on hoopis krahv Nikolai Aleksandrovitš Tolstoi, kuid sellest hoolimata jätkas ta elamist teda üles kasvatanud isa juures. Kuid Nikolai Tolstoi jättis oma pojale pärast surma 30 000 rubla ja väärika perekonnanime.[viide?]
