Его богатый дипломатический опыт был немедленно востребован, и по приезде в Петербург Толстой назначается членом Совета по иностранным делам. Он принимает деятельное участие в выработке внешней политики России, в 1715 г. удостаивается чина тайного советника и теперь именуется «министром тайного чужестранных дел коллегия». В июле того же года ведет переговоры с Данией о занятии русскими войсками острова Рюген, необходимом для быстрейшего окончания Северной войны. В 1716–1717 гг. сопровождает Петра I в его новой поездке по Европе. В ходе ее в 1716 г. Толстой участвует в сложных переговорах с польским королем Августом: вдвоем с русским послом Б.Куракиным тайный советник ведет нелегкие переговоры с английским королем Георгом I, а в 1717 г. вместе с Петром посещает Париж и пытается наладить дружественные отношения с французским правительством. Там, за границей, в Спа 1 июня 1717 г. царь поручает Толстому самую трудную и ответственную в тот момент миссию – вернуть в Россию его бежавшего во владения австрийского императора сына. Законный наследник престола мог стать козырной картой в руках враждебных России сил, которые могли таким образом получить благовидный предлог для вмешательства во внутренние дела страны. Нависшую опасность следовало устранить любой ценой. То, что подобное щекотливое поручение было возложено Петром на Толстого, свидетельствует о высокой оценке царем его дипломатической ловкости и ума. После того как русская разведка установила точное местонахождение тщательно скрываемого от посторонних глаз царевича, Толстой 29 июля 1717 г. вручил австрийскому императору письмо Петра I, где говорилось, что его сын в данный момент находится в Неаполе, и от имени своего государя потребовал выдачи беглеца. Посол тонко намекнул, что разгневанный отец с войском может появиться в Италии, а на заседании австрийского тайного совета пригрозил, что стоящая в Польше русская армия может двинуться в принадлежавшую Австрийской империи Чехию. Оказанный Толстым нажим не прошел зря – русскому послу разрешили встретиться с Алексеем и согласились отпустить его, если он добровольно поедет к отцу.

Внезапное появление Толстого и сопровождавшего его Александра Румянцева в Неаполе, где царевич считал себя в полной безопасности, поразило Алексея как удар молнии. Посол вручил ему письмо Петра I, полное горьких попреков: «Мой сын! Что ты учинил? Ушел и отдался, яко изменник, под чужую протекцию, что не слыхано... Какую обиду и досаду отцу своему и стыд Отечеству своему учинил!» Далее Петр требовал от сына возвращения, обещая ему свое полное прощение. Для Толстого потянулись дни регулярных посещений беглеца, в длительных беседах с которым он, ловко перемежая увещевания и угрозы, убеждал Алексея в полной бессмысленности дальнейшего сопротивления отцовской воле, и настоятельно советовал повиниться перед Петром и положиться на его милосердие, клятвенно заверяя его в отцовском прощении. Вряд ли проницательный Толстой питал какие-либо иллюзии относительно царской милости, и он, таким образом, сознательно выманивал Алексея в Россию на верную смерть.

Уговорив наконец Алексея вернуться к отцу, Толстой немедленно извещает государя о своем успехе. Одновременно пишет неофициальное письмо Екатерине, упрашивая ее поспособствовать в получении награды. 14 октября 1717 г. царевич вместе с Толстым выезжает из Неаполя и после трех с половиной месяцев пути прибывает в Москву. 31 января 1718 г. Толстой передает его отцу.

Обещавший простить сына Петр I не думал держать своего слова. Для розыска по делу царевича Алексея создается чрезвычайный следственный орган – Тайная канцелярия, во главе которой царь ставит продемонстрировавшего свое умение и верность Толстого. Уже 4 февраля Петр I диктует ему «пункты» для первого допроса сына. Под непосредственным руководством царя и во взаимодействии с другими «министрами» Тайной канцелярии Толстой быстро и исчерпывающе проводит расследование, не останавливаясь даже перед пытками бывшего наследника престола. Благодаря своему участию в деле Алексея бывший приверженец Милославских наконец добился царских милостей, которых так давно и страстно жаждал, и вошел в ближний круг сподвижников Петра. Наградой за жизнь царевича ему стал чин действительного статского советника и орден Св. Андрея Первозванного.