1907. január 25-én született az oroszországi Szentpéterváron, egy uráli kozák tiszt Pavel Szergejevics Tolsztov (1878–1916) és Marija Ivanovna Badajeva (1881–1924) fiaként. Nagyapja Szergej Jevlampijevics Tolsztov – lovas tábornok, a Tyereki Kozák Had vezetője, 1900–1905 között a Tyerek régió vezetője, az 1877–78-as orosz–török háború résztvevője volt. Négyen voltak testvérek.
Testvérével együtt, először a 2. Szentpétervári kadét iskolában, majd az 1917-es forradalom után az orenburgi kadét iskolában tanult. Orenburg után apja halála folytán egy moszkvai árvaházba került. 1923-ban kezdte meg tanulmányait a Moszkvai Állami Egyetemen, ahol 1930-ig először fizika és matematika szakon, majd a történelem és etnológiai szakon (antropológia szakon) tanult. Borisz Szergejevics Zsukov tanítványa volt. Hallgatói gyakorlata a Volga régióban és a türkméniai Khorezm oázisban zajlott, 1935-ben védte meg disszertációját. 1937-ben az ősi Hvárezm egykori területén kezdte meg munkáját, amelyet a Kizil-kum sivatag nyelt el. Több régészeti lelőhelyet fedeztek fel itt, köztük Toprak-Kala híres romjait is. Tolsztov az itt töltött évek alatt feltérképezte és besorolta azokat a régészeti kultúrákat, amelyek a neolitikumtól a középkorig terjedtek.
1923-tól a Moszkvai Állami Egyetemen tanult, ahol 1942 augusztusában védte meg doktori értekezését Ősi Khorezm címen, és még ugyanezen év végén a Szovjetunió Tudományos Akadémia Néprajzi Intézetének igazgatójává nevezték ki. 1943–1945-ben a Moszkvai Állami Egyetem Történelmi Karának dékánja, 1946–1966-ban a Szovetszkaja Etnografija c. folyóirat szerkesztőségét vezette. A Szovjet Tudományos Akadémia Keleti Tanulmányi Intézetének igazgatója (1950-1952). Szintén tagja volt az NDK Tudományos Akadémiájának, az Üzbég SZSZK Tudományos Akadémiájának tiszteletbeli tagja, és számos más közép-ázsiai akadémiának is tagja volt. De tagja lett a párizsi Ázsiai Társaságnak, a Párizsi Antropológiai Társaságnak, a Nagy-Britannia és Írország Királyi Antropológiai Intézetének, az Indiai Régészeti Osztálynak, a Közép- és Távol-keleti Olasz Intézetnek, a Londoni Egyetem Keleti és Afrikai Tanulmányok Iskolájának és számos más külföldi tudományos intézmény is tagjai sorába fogadta.
Életének utolsó évtizedében egy sor agyi érkatasztrófa miatt gyakorlatilag elvesztette munkaképességét. 1976. december 28-án, 69 évesen halt meg Moszkvában, a Kuncevói temetőbe temették el.
Munkássága
Elsősorban Közép-Ázsia tanulmányozásával foglalkozott, nevéhez fűződnek Toprak-Kala, Angka-Kala, Koj-Krylgan-Kala ásatásai is. Munkájáról több mint 300 tudományos publikáció jelent meg.
Alymov, Sergey (26 August 2009). "Космополитизм, марризм и прочие «грехи»: отечественные этнографы и археологи на рубеже 1940—1950-х годов" (in Russian). polit.ru. Retrieved 12 January 2016.
М.А. Итина; А.И.Першиц (16 March 2013). "С.П. Толстов — историк-востоковед, археолог, этнограф, антрополог" (in Russian). Археология Средней Азии. Retrieved 13 January 2016.
