Близ Херсона состоялась встреча еще с одной коронованной особой — австрийским императором Иосифом II. Город поразил императрицу двумя тысячами фундаментальных зданий, арсеналом, верфью. Но на Иосифа II город произвел неблагоприятное впечатление, навеянное, видимо, его недоброжелательным отношением к Потемкину. Князь и здесь организовал пышную и расточительную встречу: достаточно сказать, что дорога протяженностью в полверсты от дворца, где останавливалась Екатерина, до верфи, была покрыта зеленым сукном. Екатерина не довольствовалась ролью зрительницы, равнодушно обозревавшей Херсон, — она поспешила поделиться восторгом с Гриммом, по обыкновению несколько приукрасив увиденное: «Херсону нет еще и осми годов от роду, между тем он уже может считаться одним из лучших военных и торговых городов империи: все дома выстроены из тесаных камней; город имеет шесть верст в длину, его положение, почва, климат бесподобны, в нем по меньшей мере от десяти до двенадцати тысяч жителей всяких наций; в нем можно достать все, что угодно, не хуже Петербурга».

Екатерина выехала из Херсона 17 мая и через два дня вступила на землю Крыма. «Монархиня, — повествует Сегюр, — пожелала, чтобы во время ее пребывания в Крыму ее охраняли татары, презиравшие женский пол. Этот неожиданный опыт доверчивости удался, как великий отважный подвиг».

21 мая карета императрицы остановилась в Бахчисарае. «Там мы, — хвасталась она Гримму, — вышли прямо в дом ханов, там мы помещены между минаретами и мечетями, где кричат и молятся, поют и вертятся на одной ноге пять раз каждые 24 часа».

Сегюр нашел, что императрица, проведя в Бахчисарае пять дней, осталась крайне довольной: «В ее глазах светилась радость по поводу того, что она заняла трон ханов, которые некогда были владыками России». Состоявший на русской службе принц Нассау-Зинген, сопровождавший Екатерину, восхищался иллюминацией Бахчисарая: «С наступлением ночи все горы, окружающие город, и все дома, расположенные амфитеатром, были иллюминованы многочисленными огнями; зрелище было великолепное».

Потемкин удивил Екатерину еще одним своим творением — в Ахтиарской гавани он основал порт Севастополь. Здесь уже существовал город с укреплениями, госпиталями, четырьмястами домами, адмиралтейством и сильным гарнизоном. Но главной достопримечательностью нового города был флот: на рейде Севастопольской бухты стояло 15 кораблей, которые Екатерина в сопровождении свиты отправилась осматривать на шлюпках. «Императрица, — записал Сегюр, — находится в восторженном состоянии по поводу всего, что она видит и при мысли о новой степени величия и могущества, на которую она возводит Русскую империю». Восторгалась увиденным не только императрица, но и Сегюр: «Нам казалось непостижимым, каким образом в двух тысячах верстах от столицы в недавно приобретенном крае Потемкин нашел возможным воздвигнуть такие здания, соорудить город, создать флот, утвердить порт и поселить столько жителей. Это действительно был подвиг необыкновенной деятельности».

На другой день Екатерина наблюдала морские учения. Увиденное окончательно рассеяло все сомнения о целесообразности присоединения Крыма и укрепило веру в таланты и крайне полезную деятельность своего ученика, как она называла Потемкина. Своими наблюдениями она поделилась с московским губернатором П. Д. Еропкиным: «Весьма мало знают цену вещам те, кои с унижением бесславили приобретение сего края.