Будучи человеком смышленным, Петр Андреевич вовремя перебежал в нарышкинский лагерь, чему способствовал его родственник Федор Апраксин, но это всего лишь уберегло стольника от опалы после падения Софьи. Дороги наверх Толстому не было. При новой власти он попадает воеводой в захолустный Устюг и лишь в 1693 году по счастливому стечению обстоятельств (Петр ехал мимо в Архангельск) снова попадается на глаза царю. Должно быть, воевода сумел чем-то потрафить Петру, потому что вскоре он оказывается уже близ государя, в скромнейшем чине прапорщика – это в пятьдесят-то лет. Но в те времена служба на мелкой должности близ монарха ценилась больше, чем воеводство в глуши.

Толстой очень старается, даже получает поощрение за какие-то успехи во время второго Азовского похода, но карьера все равно не складывается. Тогда он совершает неординарный поступок. Зная, как царь поощряет людей, готовых учиться за границей, пожилой Петр Андреевич едет волонтером в Италию, где старательно обучается морскому делу, столь любимому государем.

Заручившись всеми возможными дипломами и свидетельствами, он возвращается в Москву, и царь наконец оценивает такое усердие. Моряки ему, конечно, нужны, но еще острее потребность в умных людях с опытом зарубежной жизни, да и стар Толстой для корабельной службы.

В 1702 году Петра Андреевича отправляют посланником в турецкий Адрианополь, где находился двор Мустафы II. Идет тяжелая война с Швецией, и резидент в Турции – очень важная должность. Нужно знать, следует ли опасаться нападения Порты, понимать расклад политических сил в султанском правительстве, состояние османской армии и флота. Толстой не только справляется со всеми этими задачами, но и достигает гораздо большего: он становится активным игроком в турецкой политике, интригуя против врагов России и помогая ее сторонникам. Он вербует шпионов и обзаводится «агентами влияния», раздает взятки – вообще чувствует себя как рыба в воде. Его отчеты царю деловиты и точны: «…Визирь нынешний глуп; денежной у них казны ныне малое число в сборе, а когда позовет нужда, могут собрать скоро, потому что без милосердия грабят подданных своих христиан….Ничто такого страха им не наносит, как морской твой флот; слух между ними пронесся, что у Архангельска сделано 70 кораблей великих, и чают, что, когда понадобится, корабли эти из океана войдут в Средиземное море и могут подплыть под Константинополь». (Обратим внимание, что Азовского флота турки не боятся.) Толстому удается даже, действуя через султаншу, сместить главу турецкого правительства на своего доброжелателя.