Место для порта и верфи было выбрано в 1778 г. в 30 км выше устья Днепра близ Александровской крепости. Новый город и порт назвали Херсоном. В мае 1778 г. все намеченное строительство отдавалось на попечение крупного государственного деятеля эпохи Екатерины II Екатеринославского и Таврического губернатора князя Григория Александровича Потемкина.
Для руководства постройкой нового города, верфи и эллингов на ней Адмиралтейств–коллегия направила на новую верфь своего представителя генерал–цехмейстера (главного флотского артиллериста) и флота генерал–поручика Ивана Абрамовича Ганнибала (1730–1801), дед Александра Сергеевича Пушкина). Он приступил к сооружению эллингов под корабли, для которых уже заготавливался лес вдоль Днепра в районе Могилева. Из-за нехватки работников, в особенности опытных плотников, к концу весны 1779 г. полностью готов был только один эллинг, в котором по повелению князя Г. А. Потемкина 26 мая заложили первый 60 пушечный корабль, названный в честь императрицы «Святая Екатерина».
Осенью того же года из Керчи в Днепровский лиман пришли пять 32 пушечных фрегатов и два бота, которые зимовали около Глубокой Пристани. Там к тому времени уже были построены дом для офицеров, несколько землянок и мазанок для матросов и сараев для хранения судового оборудования и судовых вещей.
К началу лета 1780 г. Ha Херсонской верфи закончилось сооружение еще двух эллингов, на которых 7 июля были заложены два 66 пушечных корабля. К середине 1781 г. там же были приготовлены еще 4 эллинга, где 23 июля торжественно заложили еще четыре 66 пушечных корабля.
Императрица Екатерина II внимательно следила за ходом создания судостроительной базы на юге России. На новой верфи постоянно не хватало работников. Императрица решила сама контролировать выполнение Адмиралтейств–коллегией требований И. А. Ганнибала по присылке достаточного количества работников всех необходимых специальностей. Уже в ноябре 1781 г. из Петербурга в Херсон прибыли 618 служителей. Князь Г. А. Потемкин организовал наем на работу государственных крестьян Поморья (побережье Белого моря), знакомых с плотничьим ремеслом.
Таким путем удалось направить на юг 1150 «мастеровых людей». По его же требованию Адмиралтейств–коллегия перевела из Казани в Херсон 300 рекрутов, а из Петербурга направила на постоянное поселение в Херсон 40 охтинских плотников, работавших до этого на верфях Петербурга. Для того времени это было довольно значительное количество новых работников для создаваемой верфи.
Наконец в январе 1783 г. императрица назначила «для командования заводимым флотом нашим на Черном и Азовском морях» одного из героев Чесмы — победного сражения 1770 г. с турецким флотом в Эгейском море — вице–адмирала Федота Алексеевича Клокачева. Так впервые в Российской империи была введена должность командующего Черноморским флотом.
В это же время для изучения недавно присоединенных к России обширных причерноморских территорий между реками Бугом и Днепром и ставшим независимым Крымом была отправлена научная экспедиция Петербургской Академии наук под руководством адъюнкта Василия Федоровича Зуева (1752–1794), будущего академика. 7 октября 1781 г. Зуев прибыл в Херсон, где приветливо был принят начальником крепости и гopoдa Херсoнa И. А. Ганнибалом.
B Херсоне за зиму Зуев привел в порядок собранные ранее в новых районах России зоологические, ботанические и геологические коллекции и часть ящиков с ними отправил в Москву. Деньги от Академии наук на содержание экспедиции так и не поступили. Выручил экспедицию Ганнибал. Он выплатил из местных средств членам экспедиции жалование за 1781 г. и первую треть 1782 г. и выдал Зуеву средства на обратное возвращение в Петербург.
Зуев посчитал возможным расширить район проведения исследований. На деньги, полученные от Ганнибала, и за счет своего жалования 20 ноября 1781 г. он отправился на русском фрегате в Стамбул. Обратный путь в Херсон, куда он прибыл 9 марта 1782 г., Зуев совершил по сухопутью через приморские районы Черного моря Болгарии, Валахии (теперь Румынии) и Бессарабии. Из Стамбула он привез собрание рыб черноморских и средиземноморских, гербарий и семена растений, произрастающих в прибрежных районах, раковины, кораллы, геологические образцы.
В письме в Академию наук Зуев описал условия плавания по морскому пути из Херсона в Стамбул, а также сообщил некоторые данные о погоде и характере волнения. Он обратил внимание на благоприятные условия для безопасного плавания по Черному морю: