Вскоре по заключении мира, в 1775 году начались заботы об отыскании на берегах Днепра места для нового порта, в котором бы можно было строить глубокосидящие морские суда и выводить их прямо в Черное море. При тщательном осмотре нижнего течения Днепра и его лимана, первоначально для устройства порта избрана была находящаяся в лимане «Глубокая пристань». Но впоследствии, когда «заведение на лимане гавани, верфи и укрепление оных» приказом возложено было на новороссийского генерал–губернатора князя Потемкина, было найдено удобнейшее для постройки порта другое место, выше Глубокой пристани, близ крепости Александр–шанц. Основанный здесь в 1778 году город назван «Херсоном», и к построению при нем порта «для скорейшего совершения сего знаменитого и государственного дела» назначен генерал–цейхмейстер Ганнибал, принимавший участие в славных боевых подвигах нашего флота в Архипелаге.
Для устройства адмиралтейства, верфи и всего нужного для порта присланы были Адмиралтейств–коллегией все необходимые морские чины и на расходы ассигнована сумма. Вместе с тем, сделано распоряжение о немедленном заготовлении лесов и других материалов для строения 7 кораблей и 4 прамов, необходимых для защиты устьев Днепра. Работа закипела, и 21 июля 1779 года на Херсонской верфи заложен был первый 66–пушечный корабль Слава Екатерины, длиной в 155 и глубиной в 16 футов. Вначале предполагали возможным строить по четыре корабля в год, но действительность не оправдала желаний. Отдаленность лесных дач, трудность доставки леса и других материалов, бесчисленные недостатки и затруднения и, наконец, повальная болезнь между служащими и рабочими до того замедлили дело, что корабль Слава Екатерины могли спустить только в 1783 году. В следующие затем три года спускали ежегодно по одному кораблю, и только с 1787 стали спускать по два. Кроме кораблей, с 1777 по 1787 год включительно, в Херсоне и на донских верфях построено было еще до 52 фрегатов, пинок и катеров, не считая малых бомбардирских и других мелких судов. Корабли того времени на нижних деках имели орудия 24–фунтового калибра; а фрегаты, пинки и катера – 16- и 12–фунтового. Но в скором времени, по мысли Потемкина, начали 24–фунтовые орудия приводить, высверливанием, в калибры 30 и 36–фунтовые и ставить их на нижних деках фрегатов и кораблей.
Строителем в Херсонском адмиралтействе был корабельный мастер Афанасьев, которым, кроме военного судостроения, положено здесь начало постройки коммерческих судов. Пример этому подал майор Фалеев, один из замечательнейших и полезнейших сотрудников Потемкина по созданию Херсона. На свой счет Фалеев строил суда и отправлял их с русской пенькой, железом и табаком за границу. В целях скорейшего развития морской торговли, для перевозки в порты Черного и Средиземного морей товаров, принадлежащих русским подданным, дозволено было отпускать казенные суда.
По отдаленности края от находящегося в Петербурге центрального морского управления, для заведывания Азовской и Черноморской флотилиями и портами, учреждено было особое «Черноморское адмиралтейское управление», находящееся в полном подчинении князю Потемкину, которому в 1785 году пожалован кейзер–флаг и предоставлено право производить в чины, до капитана 2 ранга включительно. Степень зависимости Потемкина от высшего морского начальства ясно определялась словами данного ему рескрипта: «По связи флотов наших, вы имеете в указанное время доставлять надлежащие рапорты и ведомости генерал–адмиралу». При таком положении на обязанности Адмиралтейств–коллегий осталось только исполнение всех требований князя, относящихся ко вновь заводимому флоту, в котором положено иметь двенадцать кораблей с пропорциональным числом фрегатов и других судов.
В то время, когда главнейшее внимание обращено было на устройство Херсонского порта, Россия приобрела на Черном море Другой порт, по своим удобствам уступающий разве только Босфору с его Золотым Рогом. Не наученная прежним опытом Турция в 1782 году снова нарушила мир: войска ее вступили в Тамань с намерением переправиться в Крым, где восставшее население заставило хана бежать и скрыться в Керчи под защиту русских. Но дерзкая попытка турок обратилась в пользу России: турецкие войска были скоро отброшены за Кубань, восстание крымских татар подавлено, и в следующем 1783 году полуостров окончательно присоединен к России.