Толстой — сын окольничего Андрея Васильевича Толстого. Служил с 1682 г. при дворе стольником; 15 мая этого года, в день стрелецкого бунта, энергично действовал заодно с Милославскими и поднимал стрельцов, крича, что «Нарышкины задушили царевича Ивана».
Падение царевны Софии заставило Толстого резко переменить фронт и перейти на сторону царя Петра, но последний долго относился к Толстому очень сдержанно; недоверчивость царя не поколебали и военные заслуги Толстого во 2-м Азовском походе. В 1697 г. царь посылал «волонтеров» в заграничное учение, и Толстой, будучи уже в зрелых годах, сам вызвался ехать туда, для изучения морского дела. Два года, проведенных в Италии, сблизили Толстого с западноевропейской культурой. В конце 1701 г. Толстой назначен был посланником в Константинополь, на пост важный, но трудный, к тому же отдалявший Толстого от двора.
Вернувшись в Россию в 1714 г., Толстой расположил к себе всесильного Меншикова и назначен был сенатором. В 1715 — 1719 годах Толстой исполнял разные дипломатические поручения по делам датским, английским и прусским.
В 1717 г. Толстой оказал царю важную услугу, навсегда упрочившую его положение: посланный в Неаполь, где в то время скрывался царевич Алексей со своей любовницей Евфросиньей, Толстой, при содействии последней, ловко обошел царевича и путем застращиванья и ложных обещаний склонил его к возвращению в Россию. За деятельное участие в следствии и суде над царевичем Толстой был награжден поместьями и поставлен во главе тайной канцелярии, у которой в это время было особенно много работы вследствие толков и волнений, вызванных в народе судьбой царевича Алексея.
С этих пор Толстой становится одним из самых близких и доверенных лиц государя. Сохранился дневник заграничного путешествия Толстого в 1697 — 1699 годах, характерный образчик тех впечатлений, какие выносили русские люди Петровского времени из своего знакомства в Западной Европой. Кроме того, Толстой составил в 1706 г. обстоятельное описание Черного моря.