Города Потемкина множились по мере того, как он завоевывал новые территории. Закладка еще двух новых городов стала возможной благодаря победам, одержанным во Второй русско-турецкой войне: Николаев был основан после падения Очакова, Одесса — благодаря дальнейшему продвижению России по берегам Черного моря.

Приказ об основании Николаева Потемкин подписал 27 августа 1789 года. Город был назван в честь святого покровителя мореплавателей и в память Очаковской победы (штурм Очакова произошел 6 декабря — в день св. Николая Мирликийского, особо почитаемого в России святого). Построенный на высоком, обдуваемом ветрами месте, у стечения Ингула и Буга, Николаев стал самым удачным по расположению и планировке городом, уступая только Одессе.

Город был построен Фалеевым, в соответствии с точными и исчерпывающими указаниями Потемкина. В меморандуме, содержавшем 21 пункт, князь повелевал перевести в Николаев из Херсона штаб флота, построить военную школу на 300 человек, заложить церковь на доходы от местных питейных заведений, заново отлить треснувший колокол Межигорского монастыря, добавив в него меди, построить новый монастырь, возделывать землю «по английской методе, какой обучены в Англии помощники профессора Ливанова», поставить больницы и богадельни для инвалидов, построить порт, отделать фонтаны мрамором, устроить турецкую баню и адмиралтейство — и учредить городской совет и полицию.

Удивительно, что на эти вспышки творческой активности Потемкина Фалеев отвечал столь же энергичными действиями и скоро рапортовал об исполнении. Первым делом, разумеется, сооружались верфи. Город строили крестьяне, солдаты и пленные турки: в 1789 году работали 2500 человек. Светлейший требовал от него беречь силы работников и ежедневно выдавать им горячее вино.

К октябрю Фалеев докладывал, что на земляные работы потребуется не больше месяца, а девять каменных и пять деревянных казарм уже готовы. В 1791 году из Херсона в Николаев были переведены главные судостроительные верфи. Первый фрегат сошел с николаевских доков при жизни Потемкина; дворец его был почти окончен.

Посетившая Николаев четыре года спустя Мария Гатри записала, что город имеет 100 тысяч жителей, «замечательно длинные, широкие, прямые улицы» и «красивые общественные здания». Планировка идеально расположенного города сохранилась до наших дней, хотя немногие из построек потемкинского времени уцелели. Верфи, заложенные 200 лет назад, работают на том же месте.

В 1789 году был взят турецкий форт Хаджибей — будущая Одесса. Мгновенно оценив стратегическое значение крепости, Потемкин приказал взорвать старые стены, сам выбрал место для порта и жилых построек и велел немедленно начать строительство.

Когда Потемкин умер, работы уже велись, хотя формально город основан тремя годами позже его протеже, испанцем Хосе де Рибасом. Умный, энергичный и деловой, Рибас всегда находился вблизи Потемкина — строил его корабли, командовал его флотом или добывал ему любовниц, — вместе с Поповым и Фалеевым он был одним из главных помощников светлейшего. Порт, который Екатерина назвала в честь Одессоса — древнегреческого города, находившегося, как считалось, неподалеку, — стал одной из жемчужин потемкинского наследия.

«Доношу, что первый корабль спустится «Слава Екатерины», — восторженно сообщал Потемкин императрице 1 июня 1783 года из Херсона, — позвольте мне дать сие наименование, которое я берусь оправдать и в случае действительном».