Родился в семье казачьего офицера. Некоторое время проучился в кадетском корпусе в Санкт-Петербурге, затем в Оренбурге. В 1923 г. поступил на физико-математический факультет Московского университета, но занимался на кафедре антропологии с этнографическим циклом под руководством Д.Н. Анучина. После его смерти главную роль в преподавании играл Б.А. Куфтин, во многом сформировавший Толстова, как ученого. В 1926-1930 гг. трудился в Государственном музее центрально-промышленной области (ЦПО), затем в  Музее народов СССР, где в 1939 г. открыл отдел народов Средней Азии. Многие материалы для него было собраны в этнографических экспедициях ученого. В 1939-1951 г. заведовал кафедрой этнографии Исторического факультета Московского университета. Именно он выступил основным инициатором создания кафедры. С этого времени до 1951 г. Толстов читал общий курс по этнографии для всех студентов Исторического факультета. Во время Великой Отечественной войны добровольцем ушел на фронт, был тяжело ранен в ходе битвы под Москвой. После этого был демобилизован, в 1942 г. защитил докторскую диссертацию «Древний Хорезм». В декабре того же года стал директором института этнографии АН СССР. В 1943-1944 гг. декан Исторического факультета МГУ. После войны археолого-этнографическая Хорезмская экспедиция была возобновлена, именно благодаря стараниям Толстова была открыта и изучалась эта забытая цивилизация. Проводились масштабные раскопки и исследования. В 1951 г. за монографию «Древний Хорезм» Сергей Павлович был удостоен Государственной премии СССР. Ученый активно включился в работу АН СССР, стал заместителем главного ученого секретаря Президиума АН СССР. В 1953 г. избран член-корреспондентом академии. Руководил подготовкой и изданием 18-томной серии «Народы мира». Вскоре приходит и международное признание, Толстов читал лекции в Великобритании, Франции, Италии. Входил в различные международные научные общества (Парижское азиатское и антропологическое общество).