Debiutowała w 1983 jako krytyk literacki artykułem Klejem i nożnicami (Клеем и ножницами) w czasopiśmie „Woprosy Litieratury” (1983, № 9). W tym samym roku debiutowała jako pisarz w czasopiśmie „Awrora” opowiadaniem Na zołotom krylce sidieli... (На золотом крыльце сидели…). Opowiadanie zostało pozytywnie przyjęte przez czytelników i krytykę, i uznane za jeden z najlepszych literackich debiutów lat 80. Do roku 1990 Tołstoj napisała około 20 opowiadań, które były publikowane w znanych czasopismach, m.in. w Nowym Mirie. W 1987 wydane wcześniej opowiadania zostały zebrane w zbiorze pod tym samym tytułem co jej debiut literacki – Na zołotom krylce sidieli... Za ten zbiór opowiadań została przyjęta do Związku Pisarzy Radzieckich. W 1989 stała się stałym członkiem rosyjskiego oddziału PEN Clubu.
W 1990 wyjechała do USA, by wykładać tam literaturę rosyjską w Skidmore College i Princeton oraz innych uniwersytetach. Współpracowała z amerykańskimi czasopismami New York review of books, The New Yorker, TLS i innymi. Kontynuowała pisanie esei, tym razem na temat życia rosyjskich emigrantów, w szczególności ewolucji języka rosyjskiego w różnych środowiskach. Odtąd przez całe lata 90.