Однако одного знакомства с западным образом жизни оказалось недостаточно, чтобы заслужить милость недолюбливающего его царя, и по возвращении в Россию он пребывает не у дел. Положение круто меняется, когда в апреле 1702 г. уже немолодой Толстой назначается первым постоянным русским послом в Константинополе, столице Османской империи. В тот момент это был самый тяжелый и ответственный пост всей российской дипломатической службы. Вступив в 1700 г. ради выхода к Балтийскому морю в опасную и затяжную войну со Швецией, Петр I жизненно нуждался в стабильном мире на южных границах России, поскольку войну на два фронта страна могла не выдержать. Предотвращать нападение Турции на Русь и был послан Толстой, «зело острый» ум которого и явную способность к интригам были вынуждены признавать даже его враги.

Несмотря на то что русское посольство в Константинополе было поставлено в крайне неблагоприятные условия, Толстой умудрялся добиваться успехов в исполнении возложенной на него миссии. Когда не помогали взятки и льстивые речи, русскому дипломату приходилось прибегать к интригам, в которых он был достаточно ловок. Ко всему добавлялись интриги французской дипломатии, самой влиятельной в Константинополе из европейских стран, которая, исходя из интересов своего государства, активно побуждала Турцию напасть на Россию. Колоссальные усилия посла не были напрасны – в момент решающей схватки со шведским королем Карлом XII в 1709 г. руки у Петра были развязаны, и он мог, не опасаясь удара с юга, сосредоточить все силы против главного врага.

Сокрушительный разгром шведской армии под Полтавой вызвал у турок, надеявшихся на поражение Петра и легкий захват Азова и юга Украины, взрыв ярости. Бежавших во владения султана Карла XII и изменника Мазепу встречали с небывалым почетом, и сразу же были двинуты войска к русским границам. Посол Толстой доносил канцлеру графу Г.И. Головкину из турецкой столицы: «Не изволь удивляться, что я прежде, когда король шведский был в великой силе, доносил о миролюбии Порты, а теперь, когда шведы разбиты, сомневаюсь! Причина моему сомнению та: турки видят, что царское величество теперь победитель сильного народа шведского и желает вскоре устроить все по своему желанию в Польше, а потом, не имея уже никакого препятствия, может начать войну и с нами, турками. Так они думают...» Однако Толстой в очередной раз справился со своей задачей, и уже в январе 1710 г. султан Ахмед III дает ему аудиенцию и торжественно вручает ратификационную грамоту, подтверждающую Константинопольский договор 1700 г.

Но находившийся на территории Турции шведский король не думал сдаваться. Забрав золото, вывезенное Мазепой, сделав крупные займы в Голштинии, в английской Левантийской компании и одолжив у турок полмиллиона талеров, Карл XII сумел перекупить турецких чиновников. Несмотря на все попытки Петра I и его посла сохранить мир, Великий диван высказывается за разрыв отношений с Россией, и 20 ноября 1710 г. Турецкая империя официально объявляет войну. Свое решение о войне османы дополнили актом, до которого не опускались и более дикие варварские племена, – арестом и заточением посла. В знаменитой тюрьме Пикуле, или, как ее еще называли, Семибашенном замке, он провел почти полтора года вплоть до заключения мира.

Сама эта война оказалась для России неудачной. Возглавляемая Петром I немногочисленная русская армия оказалась окруженной на Пруте превосходящими силами турецких войск. Царь был вынужден 12 июля 1712 г. подписать чрезвычайно невыгодный Прутский мирный трактат. Однако мир не наступил. Сославшись на то, что Петр I не исполнил всех своих условий мирного договора, султан 31 октября 1712 г. во второй раз объявляет России войну. Толстого опять арестовывают и бросают в Семибашенный замок, правда, на этот раз не одного, а в компании с вице-канцлером П.П. Шафировым и Михаилом Шереметевым, сыном фельдмаршала Б.П. Шереметева, присланными царем в Турцию в качестве заложников по условиям Прутского договора. Султан, видя, что на этот раз Россия основательно готовится к войне на юге, не решился идти на вооруженный конфликт и в марте 1713 г. возобновил мирные переговоры. Для ведения их русских дипломатов освобождают из константинопольской тюрьмы. Турецкое правительство предъявляет ультимативные требования: Россия должна фактически отказаться от Украины и поселить там беглых приверженцев Мазепы, а также возобновить выплату дани крымскому хану. Русские послы отвергают эти унизительные требования. Их положение чрезвычайно осложняется тем, что канцлер Головкин в этот ответственный момент оставил русских дипломатов в Турции безо всяких инструкций. Шафиров и Толстой были вынуждены самостоятельно вести тяжелые переговоры, на свой страх и риск, отвергая или принимая условия турецкой стороны. Тем не менее новый мирный договор «по многим трудностям и поистине страхом смертельным» был наконец заключен 13 июня 1712 г., и Петр, ознакомившись с его условиями, одобрил результат напряженной работы своих дипломатов. Тяжелая 12-летняя служба Отечеству в турецкой столице для Толстого закончилась, и он смог наконец вернуться на родину.