Толстой следил за развитием ситуации. Одарив турецких чиновников, он попал на аудиенцию к матери султана. Ей посол рассказал все, что знал об интригах визиря. Также через муфтия он грозил большими неприятностями для султана. Султанша передала информацию сыну. 13 января 1703 года великий визирь Далтабан был схвачен, задавлен и на должность великого визиря султан назначил Рами Мехмед-пашу, бывшего рейс-эфеиди. Крымского хана сместили. Новый визирь, «человек зело разумный», как писал Толстой, уверил русского посла в мире, «Мне ли, — говорил великий визирь, — нарушить мир, который состоялся моими трудами?» «Истиною или лукавством то говорил — бог весть, — размышлял Толстой в донесении, — уверенности никакой быть не может до тех пор, пока татарское дело прекратится и рати по домам разойдутся». Толстой сумел договориться с Портой о компенсации турецким подданным, пострадавшим от запорожцев. Российское посольство переместили в новый дом с фонтаном во дворе, что явно обозначало улучшения в русско-турецких отношениях. В ту зиму питьевую воду в турецкой столице продавали. Толстой сразу же воспользовался благоприятным моментом и расширил сферу своей деятельности, зазывая в свои покои местных и приезжих людей.
Весной 1703 года янычары выступили против султана Мустафы II. Татары, возглавляемые смещенным ханом, восстали против нового хана и султанской власти. 5–6 тысяч запорожцев, вопреки запретам царя, собирались поддержать бунтующего хана и идти на Киев или Азов. К июню восстание в Запорожье русские власти подавили.
Сторонник радикальных преобразований, Рами Мехмед-паша поощрял производство мануфактур, изготавливающих сукно и шелк. Находясь очень непродолжительное время на посту, всего лишь до августа, он сумел добиться успехов в строительстве флота. Турки начали строить крепость около Керчи Еникале (по-турецки «новая» или «Кале-и джедид»). Строительством руководил итальянец, принявший ислам, Голоппо. Так как погодные и географические условия стояли тяжелые, как писал в донесении А.П. Толстой, «место тому противитца», то строительство шло медленно. Общая численность гарнизона Еникале составила 2 тысячи человек. Одновременно турки провели работы по укреплению Очакова и Керчи — главных турецких крепостей на русско-турецкой границе.
5 июня 1703 года секретарь визиря потребовал от Толстого, чтобы русские срыли крепость Каменный Затон. Из Порты послали разведчиков в Таганрог, Азов, Воронеж. В Азов для проверки выехали капыджа-паша Шатур-Махммед-ага (Мегмет-ага) и два аги. Они остановились в предместье Азова. Турецкого посланника, отправленного осматривать 12 кораблей Азовского флота, азовский комендант не пустил даже в крепость. По прибытии в османскую столицу Мегмет-ага доложил султану о том, что русские создают морские сооружения на Дону у Азова. Султан отправил московскому царю грамоту с мутафариком Ногайлы Мустафой-агой, выразив протест. Одновременно османское правительство распорядилось о приведении турецкой границы с Россией в военное положение. Толстой имел аудиенцию с высшими турецкими сановниками. На вопрос: «Почему не пустили султанского посланника в крепость?» — он с достоинством ответил, что Мегмет-ага не имел посольского звания, поэтому и не был принят. От имени правительства российский посол отклонил притязания турок на крепость Каменный Затон. По Константинопольскому договору запрещалось строить крепости между Перекопом и Запорожской Сечью, а сооружение строилось выше Сечи. В царской инструкции, данной Толстому, говорилось, что при необходимости он может сослаться на частную смену власти в Турции, а это вынуждает Россию принимать соответствующие меры. Но Толстой решил действовать иначе. Он убедил рейс- эфенди, что крепость не имеет таких мощных укреплений, как это описывали татары. Из Москвы Толстой попросил прислать чертеж Каменного Затона. Его «выручил» силистрийский Юсуп-паша, который достал копию чертежа русской крепости и прислал ее в Стамбул. А через патриарха копия попала к Толстому.
В июне — августе бунтовщики захватили Адрианополь, султана Мустафу арестовали, новым султаном выбрали его брата Ахмеда. После прихода к власти нового султана Ахмеда III (1703–1730) Порта подтвердила условия Константинопольского договора (1700). Однако отношения между двумя государствами обострились. Толстой писал в Москву: «Новый визирь начинает чинить мне приветствование паче прежнего, но приветствования его, является мне, не столько для любви, сколько для опасения. На двор ко мне ни одному человеку пройти нельзя, потому что отовсюду открыт и стоят янычары, будто для чести, а в самом деле для того, чтоб христиане ко мне не ходили, а у французского, английского и других послов янычары не стоят. Христиане и мимо ворот моих пройти не смеют, иерусалимский патриарх с приезду моего до сих пор со мною не видался». Иерусалимский патриарх Досифей через племянника патриарха Спилиота помогал в сборе и доставке секретной информации.