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

Толстому ставилась задача собрать максимально подробную информацию о христианском населении, «выведать и описать тамошнего народа состояния». Большое значение придавалось проведению российской политики в дальних и приграничных районах Оттоманской Порты. Русский историк, лидер Конституционно-демократической партии, участник буржуазной революции 1905 года П.Н. Милюков дал точную оценку действиям российского абсолютизма: «…само русское правительство, конечно, не из идейных, а из государственных соображений поддерживало национальное самосознание. Цель этой поддержки была — противопоставить начала местной национальной культуры влиянию другой соседней культуры, более сильной и враждебной России. При этом надо заметить, что эта более сильная культура, как и везде, прежде всего, захватывала и подчиняла своему влиянию социальные верхи данной национальности. Русская же правительственная поддержка оказывалась социальным низам, принимая, таким образом, форму участия России в местной социальной борьбе на стороне демократических элементов».

В Яссах, через которые лежал путь посланника, Толстой несколько раз встречался с молдавским господарем. На тайных переговорах тот просил резидента выступить перед Петром I с ходатайством о принятии Молдавии в российское подданство, Граф Толстой не ответил ни «Да», ни «Нет». Считаясь с политической ситуацией, молдавскому господарю Петр I пожаловал княжеский титул и кавалерство.

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

Пришедший к власти в сентябре 1702 года великий визирь Далтабан Гази Мустафа-паша, по словам Толстого, был человеком ярым, безрассудным и агрессивным. Решив использовать крымских татар, он предложил тем приехать к султану и выступить за войну с русскими. В 1702 году Толстой писал Головину, что приехали в Адрианополь к султану знатные крымские мурзы. Они просят разрешить им начать войну с Россией, что «де, они, крымцы, презрены от Порты Оттоманской и в ближних от Крымского полуострова местах строятся русские города, от которых терпят они утеснение, а впредь ожидает и совершенная гибель; объявляют, будто у них есть письма от короля шведского, от поляков и от козаков запорожских — все уговаривают их вести войну с Россиею, обещаясь помогать, будто козаки с клятвою обещаются царский флот пожечь». Султан воздержался от военных действий и приказал крымчакам не нарушать мира с Россией. Тогда Далтабан написал крымскому хану тайное письмо с предложением взбунтоваться против султанской власти. Дескать, он, визирь, пойдет усмирять татар, а сам объединится с ними и совместно пойдут на Азов или Киев.

В том же году запорожские казаки, поощряемые очаковским пашой, напали на греческих купцов, приехавших на Украину. Татары послушались совета визиря и решили взбунтоваться против Порты. Крымский хан Девлет-Гирей намеревался воевать с Россией. Великий визирь начал готовиться к походу, как будто против крымчан.

Толстой следил за развитием ситуации. Одарив турецких чиновников, он попал на аудиенцию к матери султана. Ей посол рассказал все, что знал об интригах визиря. Также через муфтия он грозил большими неприятностями для султана. Султанша передала информацию сыну. 13 января 1703 года великий визирь Далтабан был схвачен, задавлен и на должность великого визиря султан назначил Рами Мехмед-пашу, бывшего рейс-эфеиди. Крымского хана сместили. Новый визирь, «человек зело разумный», как писал Толстой, уверил русского посла в мире, «Мне ли, — говорил великий визирь, — нарушить мир, который состоялся моими трудами?» «Истиною или лукавством то говорил — бог весть, — размышлял Толстой в донесении, — уверенности никакой быть не может до тех пор, пока татарское дело прекратится и рати по домам разойдутся». Толстой сумел договориться с Портой о компенсации турецким подданным, пострадавшим от запорожцев. Российское посольство переместили в новый дом с фонтаном во дворе, что явно обозначало улучшения в русско-турецких отношениях. В ту зиму питьевую воду в турецкой столице продавали. Толстой сразу же воспользовался благоприятным моментом и расширил сферу своей деятельности, зазывая в свои покои местных и приезжих людей.

Весной 1703 года янычары выступили против султана Мустафы II. Татары, возглавляемые смещенным ханом, восстали против нового хана и султанской власти. 5–6 тысяч запорожцев, вопреки запретам царя, собирались поддержать бунтующего хана и идти на Киев или Азов. К июню восстание в Запорожье русские власти подавили.

Сторонник радикальных преобразований, Рами Мехмед-паша поощрял производство мануфактур, изготавливающих сукно и шелк. Находясь очень непродолжительное время на посту, всего лишь до августа, он сумел добиться успехов в строительстве флота. Турки начали строить крепость около Керчи Еникале (по-турецки «новая» или «Кале-и джедид»). Строительством руководил итальянец, принявший ислам, Голоппо. Так как погодные и географические условия стояли тяжелые, как писал в донесении А.П. Толстой, «место тому противитца», то строительство шло медленно. Общая численность гарнизона Еникале составила 2 тысячи человек. Одновременно турки провели работы по укреплению Очакова и Керчи — главных турецких крепостей на русско-турецкой границе.

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