В Яссах Толстой несколько раз встречался с молдавским господарем. Одна из встреч была тайной, с глазу на глаз, в присутствии лишь переводчика. Предмет беседы – просьба господаря принять Молдавию в русское подданство. Что мог ответить ему Петр Андреевич? Ясно, что господарь затеял разговор не ко времени: посольство ехало в столицу империи для поддержания мира, а удовлетворение просьбы вызвало бы немедленный конфликт. Толстому пришлось употребить все свое красноречие, чтобы убедить собеседника в невозможности русскому царю «принять и иметь ево за подданного… потому что он подданной салтанской».
10 августа посольство переправилось через Дунай, и теперь уже его сопровождали османские приставы. Они множество раз извинялись за то, что не поспели к Сороке, и заверяли, что султан и везир велели, чтобы в дальнейшем «послу чинено было великое почтение… и довольство паче всех прежде бывших послов».
29 августа посольство без особых приключений достигло Адрианополя, где тогда находился султанский двор, а обещанной «чести», равно как и роскошных палат, не предвиделось. Встреча посольства оказалась не столь пышной, как обещали послу; в скромном доме, отведенном представителям России, Толстому пришлось довольствоваться лишь одной палатой, в то время как его предшественники – Украинцев и Голицын – имели по три.
Началось томительное ожидание аудиенций у везира и султана в стране, где у Петра Андреевича не было ни знакомых, ни друзей, ни связей. Все это предстояло заводить ему самому, равно как и завоевывать к себе уважение. Для Толстого это была нехоженая тропа. Перед ним возникло столько непредвиденного, что, не будь он таким незаурядным человеком, не владей он даром располагать к себе людей и пользоваться их услугами, наверняка допустил бы массу оплошностей и ошибок. Да и сам Толстой начал с действий, свидетельствовавших о его неосведомленности не только относительно порядков в стране пребывания, но и о дипломатическом этикете вообще.
Человек деятельный и практичный, Петр Андреевич рассуждал, по-видимому, так: раз он отправлен с ясной, четко сформулированной целью, то, прибыв на место, надобно без промедления приступить к ее достижению. Однако случилось неожиданное. Правительство Османской империи накануне приезда русского посольства оказалось без главы: старый везир умер, а новый еще не приступил к исполнению своих обязанностей. Толстой полагал, что отсутствие везира не помеха, и стал настойчиво добиваться аудиенции у султана. И сколько ему ни втолковывали, что обычаи исключают аудиенцию у султана до встречи с везиром, он продолжал настаивать на своем.