В 1694 г. Толстой вернулся на военную службу и получил чин прапорщика. В 1696 г. во время взятия Азова он был уже капитаном гвардейского Семеновского полка. Стремясь завоевать доверие Петра I, Петр Андреевич в 1697 г., в возрасте 52 лет, будучи уже дедушкой, испросил у царя разрешения отправиться волонтером в Италию изучать военно-морскую науку. Растроганный такой просьбой, Петр направляет Толстого на учебу в Италию.
26 февраля 1697 г. Толстой выехал из Москвы, имея при себе инструкцию царя с перечнем знаний и навыков, которыми он должен был овладеть в Италии. Главное, чему Петр Андреевич должен был научиться, — это умение пользоваться морскими картами, водить корабли и управлять ими во время сражения. Толстой побывал во многих городах Италии, изучил итальянский язык, освоил кораблевождение и множество морских профессий. Но не море стало родной стихией П. А. Толстого. Царь Петр нашел ему иное назначение. Петру Андреевичу Толстому по возвращении на родину в феврале 1697 г. предстояло послужить России на поприще тайной дипломатии.
Дипломатическая деятельность Толстого протекала в один из самых сложных периодов Северной войны. Задача русской дипломатии после поражения под Нарвой заключалась в том, чтобы предотвратить выступление Османской империи против России. Петру Андреевичу предстояло утвердиться в Стамбуле в качестве постоянного дипломатического представителя России. Он стал первым русским дипломатом, возглавившим не временное, а постоянное посольство в столице Османской империи.
Указ о назначении Толстого послом в Стамбул датирован 2 апреля 1702 г. 22 мая 1702 г. посольство покинуло Москву. В конце августа оно без особых приключений прибыло в Адрианополь, где тогда находился двор султана. При себе Толстой имел наказ Петра в виде «тайных статей», представлявших собой разведывательное задание из 17 параграфов. Османское правительство сделало все возможное для того, чтобы изолировать русское посольство от внешнего мира и лишить посла возможности общаться с кем бы то ни было. Однако на помощь Толстому пришли доброжелатели. Сам он их называл «работниками». Именно от «работников» Петр Андреевич получал всю необходимую информацию.
Первым среди них был иерусалимский патриарх Досифей. О его готовности оказывать помощь русским послам хорошо знали в Москве, поэтому одновременно с полномочной грамотой Толстому направили грамоту и Досифею. Вместе с Досифеем сотрудничал с русскими и его племянник Спилиот, тоже грек. Он выполнял иногда роль курьера в переписке патриарха с послом. Сотрудничество Досифея с Толстым оказалось на редкость плодотворным и полезным для России. Не менее ценные услуги оказывал Толстому серб Савва Лукич Владиславич, по русским источникам более известный под фамилией Рагузинский (он был выходцем из Рагузы — так латиняне называли город Дубровник). После отъезда Владиславича в 1704 с в Россию его обязанности перешли к его приятелю Луке Барке.
В сентябре 1703 г. двор султана, центральные учреждения и все посольства переехали из Адрианополя в Стамбул. Истекший год оказался знаменательным для Толстого. Он подготовил и отправил в Москву сочинение под названием «Состояние народа турецкого». Это был ответ посла на секретные пункты инструкции. Петр Андреевич подробно описал структуру государственного аппарата Османской империи, круг обязанностей высших чиновников, отметив, что радеют «…все турецкие министры больше о своем богатстве, нежели о государственном управлении».
Метко и лаконично Толстой описал отношения Порты с европейскими странами. Так, например, об османо-австрийских отношениях он писал: «Сердечного любления к цесарскому народу не имеют и пущей злобы не являют, и народ цесарской в войне сильной и искусной». По достоинству в Москве оценили сведения Петра Андреевича об организации вооруженных сил империи, о мобилизации янычар на случай войны. Интерес представляла также информация о способах доставки к театру военных действий снаряжения, вооружения и продовольствия.
Важные сведения Толстой добыл о военно-морских силах Турции. Посол сообщал не только о типах кораблей, их вооружении, укомплектованности экипажей, о верфях, но и о сигнализации, подготовке кораблей к бою и боевых порядках во время морских сражений.
В 1703 г. Толстой сумел предотвратить вторжение на территорию России совместных войск крымского хана и турок. Он узнал о том, что великий визирь Далтабан за спиной султана отправил янычар для соединения с крымскими татарами, чтобы совместно выступить против России. Трудность заключалась в том, как уведомить султана о планах визиря. Толстой нашел подход к матери султана и рассказал обо всем ей и муфтию, а те, в свою очередь, султану. Судьба визиря была решена. Угроза войны отдалена.
С 1704 г. при дворе султана увеличилось число противников России, за которыми Толстому надлежало следить «недреманным оком». К традиционно враждебным крымским татарам прибавились поляки, поддерживавшие С. Лещинского, шведы, И. С. Мазепа и, наконец, французский посол. Так, весной 1707 г. Петр Андреевич установил, что французский посол Ферриоль через крымского хана изо всех сил пытался поссорить Османскую империю с Россией. Французский дипломат убеждал Порту в том, что если она «…в нынешнем времени московского царя не утеснит, уже-де впредь долго такого времени дожидаться». При этом Ферриоль, по словам Толстого, «не жалел иждивения» и чинил «туркам великие дачи». Петр Андреевич своевременно отреагировал на закулисные интриги французского посла. Он сумел найти способ вручить письмо султану с разоблачением интриг крымского хана и французского посла. В результате султан решился сменить крымского хана. Место воинственного хана Кази-Гирея занял Каплан-Гирей, которому велено было «с Московским государством жить смирно».
Петр I по достоинству оценил успех своего посла. 20 мая 1707 г. Петр Андреевич получил письмо главы Посольского приказа Г. И. Головкина с извещением о пожаловании ему «за усердную службу и труды» вотчины.
В целом деятельность Толстого в 1707 г. была весьма полезной для России. Ему удалось парализовать выпады французского посла, а также отразить попытки крымского хана, Станислава Лещинского и Карла XII вбить клин в отношения между Османской империей и Россией. Однако в начале следующего 1708 г. Петру Андреевичу пришлось столкнуться с неприятностью с той стороны, откуда он ее не ожидал. Толстой получил из Москвы копию письма гетмана Мазепы с сопроводительным письмом Головкина и указом Петра I. Содержание письма Мазепы от ноября 1707 г. противоречило информации Толстого о положении дел в Стамбуле. Головкин выражал недовольство службой посла, а Петр прямо писал: «Господин посол, посылаем к вам о некотором деле письмо, здесь вложенное, на которое немедленной желаем отповеди».
Мазепа сообщал, что его лазутчик, вернувшийся из Молдавии, доставил сведения огромной важности. Суть их заключалась в непременном намерении Турции напасть на Россию. В письме гетман подробно перечислял военные и дипломатические меры, которые предпринимала Оттоманская Порта, готовясь к войне. К ним относились отправка в Бендеры 200 пушек и срочное пополнение гарнизона крепости. Из письма гетмана следовало, что визирь ведет тайные переговоры со Станиславом Лещинским и шведским королем о том, чтобы не заключать мира с Россией без согласия султана. В свою очередь поляки и шведы склоняли османов к войне с Россией, заявляя, что для этого наступило самое благоприятное время, «какого впредь не могут иметь». Все эти приготовления, доносил гетман, ведутся за спиной ничего не подозревающего русского посла.
В подтверждение своей правоты Мазепа ссылался-на иерусалимского патриарха, который якобы откровенно писал гетману: «Порта непременно со шведом и с Лещинским хочет и самим делом склоняется в союз военный вступить и войну или зимою, или весною с его царским величеством начать». Более того, Досифей будто бы выказал Мазепе недовольство тем, что в Москве «не внимают» его донесениям и что он, огорченный невниманием, более не будет писать на эту тему.
В конце января 1708 г. Толстой получил от Головкина еще одно письмо. В нем сообщалось, что сведения о «турецком злом намерении» заключить военный союз против России «от часу умножаются и отовсюду неустанно на всех почтах приходят как из Вены… так и от протчих наших министров из Англии и Галандии и из Берлина». Головкин резко отчитывал Толстого за бездействие: «Немалому то удивлению достойно, что ваша милость незнамо для чего ни о чем о том нам ни малой ведомости не чинишь и не престерегаешь того, для чего вы у Порты от его царского величества быть учреждены и в чем весь интерес состоит».
Необходимо отдать должное Петру Андреевичу Толстому. Он мужественно со всей страстностью и упорством вступил в полемику с Головкиным, отстаивая свою правоту. Располагая точными сведениями, Толстой решительно заявил, что лазутчик Мазепы лжет о концентрации артиллерии и янычар в Бендерах. По его сведениям, в Бендеры было прислано 500 янычар, из которых 300 разбежались, а пушек отправили столько, сколько требовалось для обороны крепости. Нетрудно было ему доказать и необоснованность утверждения Мазепы о якобы ожидаемом нападении крымских татар зимой, а главных сил османской армии весной. В письме от 29 января 1708 г. Толстой писал, что зима на исходе, а «войны от татар не слышится, и весна уже приближается, а у турок никакого приготовления к войне не является».
