Между тем Иосиф уже прибыл в Херсон и ожидал там императрицу. Иосиф предпочитал путешествовать налегке и снова отправился в путь под именем графа Фалкенштейна. С небольшим багажом в компании единственного конюшего и двух слуг он обычно быстро добирался до пункта своего назначения. В Херсоне он подождал некоторое время императрицу, а затем решил двинуться вверх по реке, чтобы встретить Екатерину в Кременчуге, где флот из галер должен был замедлить ход около первого из порогов Днепра. Когда галеры прибыли в Кременчуг, Екатерине сообщили, что граф Фалкенштейн ожидает ее в Херсоне. Вскоре пришла следующая новость: он уже двинулся в путь и направился в Кременчуг. Не желая быть застигнутой врасплох, Екатерина быстро сошла на берег и в карете поспешила навстречу союзнику. Они встретились на дороге, а после вместе поехали в ее карете и вернулись в Кременчуг, находившийся неподалеку. Присоединившись к путешественникам, Иосиф настоял на сохранении своего инкогнито, присутствовал на приеме вместе с другими придворными, где был представлен как граф Фалкенштейн. Он был рад видеть своего друга и командующего армией Линя, а также нашел нового друга – Сегюра. Иосиф с восхищением говорил с французским послом о необычайно энергичной женщине, которая стала его союзницей и была на десять лет старше его. В адрес Мамонова он высказал лишь несколько комплиментов: «Новый фаворит хорош собой, – писал Иосиф, – но не производит впечатления умного человека. Складывается впечатление, что его пугает собственное положение, и он кажется всего лишь испорченным ребенком».
Проведя в Кременчуге сутки, Екатерина и Иосиф покинули придворных, предоставив им сомнительное удовольствие преодолевать пороги Дона на галерах, а сами в карете отправились к Екатеринославу, возведением которого занимался Потемкин. Там в присутствии Иосифа Екатерина положила первый камень в основание нового городского собора. Император, сомневавшийся, стоит ли строить большую церковь до того, как город отстроен и заселен жителями, писал другу в Вену: «Сегодня я совершил большое дело. Императрица положила первый камень в фундамент новой церкви, а я – последний».
Когда галеры благополучно преодолели пороги, оба правителя снова сели на корабль и добирались до Херсона уже по воде. Девятью годами ранее, когда Потемкин только выбирал это место, находившееся в двадцати милях от Черного моря, Херсон был всего лишь маленьким поселком на болотах. Теперь же он превратился в город-крепость с двумя тысячами белых домов, прямыми улицами, раскидистыми деревьями, цветущими садами, церквями, административными зданиями, и бараками, в которых размещалось двадцать тысяч человек. На улицах было много людей, магазины ломились от продуктов, процветающая судоверфь с пакгаузами были возведены вдоль набережной, а два полностью построенных линейных корабля и один фрегат готовились к спуску на воду. Более сотни кораблей, многие из которых были русскими, стояли на якоре в порту. 15 мая Екатерина и Иосиф участвовали в спуске на воду трех кораблей, включая линейный корабль «Владимир» и мощный линейный корабль с восемьюдесятью пушками, названный «Святым Иосифом».
Близость Турции волновала мысли обоих правителей. Они видели арку, которую возвел Потемкин у входа в город и на которой была выгравирована провокационная надпись на греческом: «Дорога на Византию». Они встретились с Яковом Булгаковым, русским послом в Константинополе, который прибыл, чтобы отчитаться перед императрицей и сообщить ей о том, что им с Потемкиным уже было известно: Османская империя так и не признала присоединение Крыма и наличие для России выхода к Черному морю. Турки лишь выжидают удобный момент, предупредил ее Булгаков. Екатерина и Потемкин понимали, что в ближайшие два года Россия будет еще не готова к войне, и поэтому велели Булгакову приложить все усилия, чтобы сохранить в течение этого времени мирные отношения.
Сама Екатерина теперь должна была соблюдать осторожность. Изначально она надеялась проплыть по всему Днепру и из Херсона по устью реки направиться к Черному морю. Турки воспрепятствовали ее намерениям совершить последний этап путешествия по реке, послав четыре военных корабля и десять фрегатов в устье реки. Это послужило напоминанием о том, что Днепр еще не являлся полностью открытой рекой.