Несмотря на разочарование, Екатерина намеревалась произвести впечатление на своего царственного союзника и иностранных послов и взяла их с собой в поездку по Крыму. Покинув Херсон 21 мая, они продолжили путешествие по суше в каретах. Оказавшись в степи, Иосиф был потрясен, когда неожиданно перед ними в облаке пыли появились двенадцать сотен татарских всадников; это были кочевники, чьи земли лишь недавно присоединились к империи, однако они уже были преданы Екатерине и готовы служить ей почетной охраной. Пораженный зрелищем Иосиф покинул в сумерках лагерь и вместе с Сегюром совершил прогулку по степи, простиравшейся до самого горизонта. «Какая необычная земля, – сказал император, – и кто мог ожидать, что я вместе с Екатериной Второй, французским и английским послами буду путешествовать по татарской пустыне? Какая замечательная страница в истории!»
Во время переезда через Перекопский перешеек, соединяющий Крымский полуостров с Украиной и Россией на севере, процессия из экипажей двигалась по крутой, каменистой дороге, ведущей к Бахчисараю – бывшей столице крымского ханства. Там, в покоях ханского дворца, была создана временная резиденция для двух монархов. Несколькими месяцами ранее Екатерина отправила Чарльза Камерона, шотландского архитектора, восстановить и украсить дворец. Камерон сохранил атмосферу ислама. Там были внутренние дворы и потайные сады, окруженные высокими стенами и живой изгородью из миртовых деревьев; прохладные, простые по убранству комнаты со стенами, выложенными разноцветными изразцами, толстыми коврами, искусно выделанными гобеленами, а в центре каждой комнаты располагался мраморный фонтан. Из открытого окна Екатерина могла видеть минареты, возвышавшиеся над стенами дворца, и вдыхать запах роз, жасмина, апельсиновых и гранатовых деревьев. Вокруг дворца расположился город, в котором находилось девятнадцать мечетей с высокими минаретами, откуда пять раз в день голос призывал правоверных на молитву. Во время своего пребывания в городе Екатерина распорядилась возвести еще две мечети. За пределами дворца также повсюду были видны, слышны и ощутимы все признаки исламской страны: шумные городские базары, татарские мужчины в длинных одеждах, их жены, полностью скрывавшие себя за длинными одеждами и позволявшие видеть лишь свои глаза.
Поскольку Потемкин стремился показать Екатерине и императору свое самое большое достижение на юге, они провели в Бахчисарае только три дня и две ночи. 22 мая путешественники направились в горы через заросли сосен и кипарисов к изрезанному скалистому мысу южного черноморского побережья Крыма. Здесь они оказались в прекрасном, похожем на Ривьеру месте, где климат был мягким круглый год, где росли оливковые деревья, виноградники, фруктовые деревья, жасмин, лавр, сирень, глицинии, розы и фиалки. Каждой весной буйное цветение фруктовых деревьев, кустарников, вьющихся растений и диких цветов превращало побережье в огромный благоухающий сад.
Пунктом их назначения был Инкерман – находившаяся на возвышении крепость с видом на Черное море, где они обедали в новом павильоне. После полуденного банкета Потемкин встал и отодвинул полог одной из стен шатра. Путешественники увидели под безоблачным голубым крымским небом амфитеатр из морщинистых вершин гор, поднимавшихся над изумрудно-голубой водой. Залив Севастополя сверкал в лучах солнца. В порту стояли корабли Черноморского флота, разросшегося стараниями Потемкина. По сигналу из павильона корабли дали торжественный залп в честь двух монархов. По завершении салюта один из новых кораблей поднял флаг императора и салютовал специально для него.
Екатерина повела Иосифа к карете и вместе они отправились в порт, чтобы осмотреть пристань и город. Они увидели новые верфи и пристани, оборонительные сооружения, склады боеприпасов, бараки, церкви, две больницы, магазины, дома и школы. Иосиф, который во время визита в Херсон пребывал в довольно скептическом настроении, был поражен Севастополем, по его словам, это был «самый красивый порт, который ему доводилось видеть». Впечатленный высоким качеством исполнения и боевой готовностью российских кораблей, император добавил: «Здесь нужно побывать лично, чтобы поверить тому, что я увидел».
Из Севастополя Екатерина намеревалась провести своих гостей по Крыму, а затем направиться в Таганрог на Азовском море. Но летняя жара и намерение Иосифа вернуться в Вену убедили ее остановиться. Они сели в карету и вернулись к Днепру, по дороге обсуждая политику и планы на будущее. 2 июня они расстались. Екатерина продолжила путешествие на север, в Полтаву, где Потемкин воссоздал битву при Полтаве 1709 года, во время которой Петр Великий разгромил шведскую армию Карла XII, вторгшуюся в Россию. Екатерина наблюдала за тем, как пятьдесят тысяч русских солдат, часть которых была переодета в русскую форму, а часть – в шведскую, разыгрывали знаменитую битву.