Родился в Крыму в местечке Ачкора. Сын графа Александра Николаевича Толстого и Клавдии Дмитриевны Быстролетовой. В 1904-1914 гг. жил в Петербурге, в семье графини де Корваль, где получил домашнее образование и воспитание. В 1915-1917 гг. учился в Севастополе в Морском кадетском корпусе. Участник Первой мировой войны на Турецком театре военных действий. В 1919 г. дезертировал из армии Деникина и бежал в Турцию. С отличием окончил выпускной класс колледжа для европейцев-христиан в Константинополе. В Чехословакии поступил в университет.
В 1923 г. в Праге получил советское гражданство. Работал в торгпредстве СССР. С 1925 г. — штатный сотрудник внешней разведки, в 1930-1937 гг. — нелегал. Продолжая образование, стал доктором права Пражского университета, доктором медицины Цюрихского университета, учился в Берлинской и Парижской академиях художеств, изучил двадцать иностранных языков. Объездил многие государства Азии, Африки, Америки и Европы. Жил среди туарегов в пустыне Сахаре, среди пигмеев в Экваториальной Африке, в среде аристократов Англии, Франции и Италии, промышленников и банкиров Германии, Америки и Голландии.
В 1937 г. приехал в СССР, в том же году стал членом Союза художников СССР. В сентябре 1938 г. арестован. Обвинен по 58-й статье, п. 6, 7, 8 УК РСФСР. Далее — по «сталинской путевке» — полная программа ГУЛАГа: в заполярном Норильске, в Краслаге, в Сиблаге, в одиночной камере спецобъекта «Сухановки», на советской каторге в Озерлаге и Камышлаге. Освобожден в 1954 г. (сактирован как инвалид). Реабилитирован в 1956 г. Жена (и сотрудница) Быстролетова Шелматова Миле-на Иоланта Мария покончила с собой после ареста мужа.
После освобождения жил в Москве, работал над книгами, мемуарами, сценариями. В ноябре 1973 г. состоялась премьера художественного фильма «Человек в штатском» по сценарию Быстролетова. Похоронен в Москве на Хованском кладбище.
Быстролетов — автор шестнадцати книг и мемуаров, в которых дает свое видение обстановки в стране накануне Второй мировой войны, оценку действий руководящих органов советского государства и Сталина.
