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

Вечером в Бахчисарае приветственной иллюминацией озарились все мечети и жилое строение, «расположенное косогором». В главной мечети, где были похоронены ханы и члены их семей, муфтий с дервишами совершил торжественное богослужение.

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

Стены дворца еще помнили былых владельцев, шепот и стенание наложниц гарема. Спустя годы здесь оказался великий Пушкин, уловив своим поэтическим слухом то, что, может быть, чувствовали Екатерина и Потемкин в Бахчисарайском дворце:

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

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

Из Бахчисарая путь Екатерины II лежал к Черному морю. 22 мая 1787 г. императорское шествие достигло Инкермана.

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

После знаменательного обеда Екатерина в сопровождении императора Иосифа II, дипломатов и придворных вельмож на шлюпках отправилась «по заливу к городу Севастополю». При приближении к флоту на катере императрицы был поднят штандарт, и тогда все корабли, фрегаты и другие суда, спустя свои флаги, салютовали из всех пушек. Матросы, стоящие по реям, вантам и борту, неистово громко и многократно кричали «ура! ура! матушке Екатерине!». Когда катер с государыней поравнялся с флагманским кораблем, то каждое судно сделало 31 выстрел, заглушая восторженные крики матросов. Существование боеспособного Черноморского флота даже самые непримиримые противники и критики князя не могли подвергнуть сомнению, ведь нельзя же всерьез говорить о том, что нарисованные корабли столь оглушительно стреляют и живо маневрируют. Вид флота из 27 военных судов и 8 транспортов убедил всех, включая иностранных очевидцев, в возможности России удержать приобретенные земли. Сегюр заметил Екатерине, что своими достижениями она загладила воспоминания о неудачном Прутском походе Петра I, запорожских «разбойников» превратила в полезных подданных и подчинила татар, прежних поработителей России. «Наконец основанием Севастополя, — заключил французский дипломат, — вы довершили на юге то, что Петр начал на севере». Она благосклонно приняла восторги Сегюра и уточнила, что, не будь у нее такого соратника, как Потемкин, вряд ли бы достижения были столь значительными и успешными.