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