В июне — августе бунтовщики захватили Адрианополь, султана Мустафу арестовали, новым султаном выбрали его брата Ахмеда. После прихода к власти нового султана Ахмеда III (1703–1730) Порта подтвердила условия Константинопольского договора (1700). Однако отношения между двумя государствами обострились. Толстой писал в Москву: «Новый визирь начинает чинить мне приветствование паче прежнего, но приветствования его, является мне, не столько для любви, сколько для опасения. На двор ко мне ни одному человеку пройти нельзя, потому что отовсюду открыт и стоят янычары, будто для чести, а в самом деле для того, чтоб христиане ко мне не ходили, а у французского, английского и других послов янычары не стоят. Христиане и мимо ворот моих пройти не смеют, иерусалимский патриарх с приезду моего до сих пор со мною не видался». Иерусалимский патриарх Досифей через племянника патриарха Спилиота помогал в сборе и доставке секретной информации.

Большую помощь оказывал русскому посланнику выходец из Рагузы серб Савва Лукич Владиславович-Рагузинский. Затаив в душе ненависть к османским правителям — разорителям его родового гнезда, Савва искал силу, которую можно было бы направить против Турции. Сотрудничество Толстого и Рагузинского было обоюдным. С приходом Ахмета III положение Саввы переменилось, за ним установили надзор, запретили выезжать из страны. Рагузинский к тому времени имел хорошо поставленную торговую и разведывательную сеть. Опасаясь за свою дальнейшую судьбу, он решил бежать из Османской империи. В 1704 году Савва переехал в Россию, передав свои дела с российским послом тоже сербу, Луке Барке, — консулу Рагузинской республики в Турции. О Рагузинском Толстой написал царю рекомендательное письмо: «Савва человек добр и до сего времени усердно в делах великого государя работал, и видится, что и впредь желание имеет служить верно». Царю Рагузинский представил составленный им труд «Изучение дороги Черным морем в Москву». В рукописи Савва дал сведения о гарнизонах, портовых сооружениях, вооружении турецкой армии, местах базирования флота. Петр I выделил ему ежегодный пансион в 325 рублей, дом в Москве на Покровке, право беспошлинной торговли на 10 лет.

На Балтике полным ходом шли приготовления. Войска подтягивались в нарвском направлении. Головин, обеспокоенный положением на юге, спрашивал Толстого, нельзя ли занять турок и направить их против австрийцев, тем самым исключить возможность войны с Оттоманской Портой? Толстой отвечал в январе 1704 года: «По приказу твоему начинаю к тому приступать самым секретным образом чрез приближенных к султану людей, но еще пользы не вижу никакой; главное препятствие в том, что нечего давать, и хотя бы и было что дать, боюсь потерять; француз потерял больше ста тысяч реалов, а пользы себе никакой не получил. Сыскал я одного человека, самого близкого к султану; человек этот очень проворен, он взялся за дело, однако не уверяет, что приведет его к концу, больше склоняется к войне с Венециею. Посулил я ему 3000 золотых червонных, если сделает дело, но он говорит, что и другим дать надобно, всего тысяч сорок золотых червонных, кроме его 3000. Он же мне говорил, чтоб промыслить прежде всего султану мех лисий черный самый добрый, да три сорока соболей, по сто рублей пара, и отослать бы эти подарки султану тайно чрез него, а будет ли от того прок или нет, не уверяет».

Головин, соизмерив затраты и возможности, попросил Толстого отступить от дела. Подарки из Москвы для турецких чиновников выслали. «Здесь все смирно, — доносил Толстой весной 1704 года, — турки покою ради, и которые мне трудности были от татарских ложных клевет, ныне умолкли; визирь ко мне очень ласков и со мною обходится пристойно, как с другими послами; свобода мне ездить куда хочу, и ко мне всех пускают; устроилось это не иным, чем только казною великого государя; хотя бы кто был и умный человек, а без подарков получить этого у турок не мог бы».

После отъезда Рагузинского Толстой продолжил активную разведывательную деятельность. Валашский господарь Брынковяну снабжал Толстого деньгами, посылал сведения о политическом, военном, экономическом положении Оттоманской Порты. Данные, которые предоставляли информаторы Толстому, а тот, в свою очередь, в Москву, были разнообразными, не дающими точного суждения о военной силе османов, характере наступательных действий, стратегическом плане турок и татар на Дунае, — разве что отдельные фрагменты, по которым нельзя было предположить общий ход развития будущей войны. В целом сотрудничавшие с русским послом лица показывали течение событий как благоприятное для наступления русских на Балканы.

В 1704 году сербский полковник Пантелеймон Божич, бывший комендант крепости Тителы, располагавшейся на месте впадения реки Тисы в Дунай, вел переговоры с Ф.А. Головиным, возглавлявшим Посольский приказ, об эмиграции сербов Австрийской империи в Россию. Массовый выход сербов в Россию мог бы осложнить русско- австрийские отношения, что явно было на начальном этапе Северной войны очень некстати. Миграционный поток остановили. После перехода на русскую службу на П. Божича возлагалась ответственная миссия: быть представителем и посредником сербского народа.

В июле того же года в Польше шляхта избрала королем ставленника Карла XII Станислава Лещинского. Толстой получил сведения о том, что крымский хан решил объединить свои силы с поляками против русских, и просил султана разрешить напасть на Приднепровье. Русские войска поддержали низложенного Августа II, сосредоточившись в районе Гродно. Возглавили поход Петр I и Ф.А. Головин. По русско-польскому договору под Нарвой от 19 августа 1704 года русское правительство обязалось выделить в помощь польскому королю 12-тысячный русский корпус и ежегодную субсидию в 200 тысяч рублей на содержание 48 тысяч солдат, выставляемых поляками для борьбы против шведов, до окончания военных действий. Шведы отрезали путь русской армии, стремившейся воссоединиться с войсками Августа II. Правительство Станислава отправило письмо в Порту, в котором отмечалось, что русские собираются завоевать Каменец, а с ним и всю Подолию, а дальше для русской армии при поддержке молдаван, валахов и других христианских народов Турции, как писал информатор, не составит труда занять всю территорию от Днестра до Дуная. Толстой сумел подарками «нейтрализовать» клеветников. Русский резидент о политике Ахмеда III писал: «О начатии войны в какую-нибудь сторону вовсе не слышится».

В 1704 году Толстой вплотную занялся поиском и выкупом пленных русских. Из Порты распоряжения о содействии российскому послу направили силистрийскому сераскиру Юсуф-паше, которому подчинялся приграничный Бендерский гарнизон на Днестре, капитан-паше Керчи, крымскому хану. Толстой активно вел переговоры о торговых отношениях с Турцией через Черное море. Государственный канцлер, президент Посольского приказа Ф. А, Головин, будучи еще и начальником Военно-морского приказа, в рекомендации Толстому предложил туркам сделку. Если турки согласились бы не вывозить из страны оружие и военные запасы, то русское правительство могло продать им азовские корабли по сходной цене, а также не возражало против постройки новой турецкой крепости недалеко от Очакова. Турецким купцам предоставлялась полная свобода вывоза товаров из России за исключением пленных. Но послу недвусмысленно ответили из султанского дворца: «Османская империя не потерпит появления на Черном море не только русских кораблей, но даже парусника или двухвесельной лодки». Как объяснил министр иностранных дел Толстому, султан смотрит на Черное море как на свой дом, куда нельзя пускать чужестранцев.