Близость Турции волновала мысли обоих правителей. Они видели арку, которую возвел Потемкин у входа в город и на которой была выгравирована провокационная надпись на греческом: «Дорога на Византию». Они встретились с Яковом Булгаковым, русским послом в Константинополе, который прибыл, чтобы отчитаться перед императрицей и сообщить ей о том, что им с Потемкиным уже было известно: Османская империя так и не признала присоединение Крыма и наличие для России выхода к Черному морю. Турки лишь выжидают удобный момент, предупредил ее Булгаков. Екатерина и Потемкин понимали, что в ближайшие два года Россия будет еще не готова к войне, и поэтому велели Булгакову приложить все усилия, чтобы сохранить в течение этого времени мирные отношения.

Сама Екатерина теперь должна была соблюдать осторожность. Изначально она надеялась проплыть по всему Днепру и из Херсона по устью реки направиться к Черному морю. Турки воспрепятствовали ее намерениям совершить последний этап путешествия по реке, послав четыре военных корабля и десять фрегатов в устье реки. Это послужило напоминанием о том, что Днепр еще не являлся полностью открытой рекой.

Несмотря на разочарование, Екатерина намеревалась произвести впечатление на своего царственного союзника и иностранных послов и взяла их с собой в поездку по Крыму. Покинув Херсон 21 мая, они продолжили путешествие по суше в каретах. Оказавшись в степи, Иосиф был потрясен, когда неожиданно перед ними в облаке пыли появились двенадцать сотен татарских всадников; это были кочевники, чьи земли лишь недавно присоединились к империи, однако они уже были преданы Екатерине и готовы служить ей почетной охраной. Пораженный зрелищем Иосиф покинул в сумерках лагерь и вместе с Сегюром совершил прогулку по степи, простиравшейся до самого горизонта. «Какая необычная земля, – сказал император, – и кто мог ожидать, что я вместе с Екатериной Второй, французским и английским послами буду путешествовать по татарской пустыне? Какая замечательная страница в истории!»

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