По отдаленности края от находящегося в Петербурге центрального морского управления, для заведывания Азовской и Черноморской флотилиями и портами, учреждено было особое «Черноморское адмиралтейское управление», находящееся в полном подчинении князю Потемкину, которому в 1785 году пожалован кейзер-флаг и предоставлено право производить в чины, до капитана 2 ранга включительно. Степень зависимости Потемкина от высшего морского начальства ясно определялась словами данного ему рескрипта: «
В то время, когда главнейшее внимание обращено было на устройство Херсонского порта, Россия приобрела на Черном море Другой порт, по своим удобствам уступающий разве только Босфору с его Золотым Рогом. Не наученная прежним опытом Турция в 1782 году снова нарушила мир: войска ее вступили в Тамань с намерением переправиться в Крым, где восставшее население заставило хана бежать и скрыться в Керчи под защиту русских. Но дерзкая попытка турок обратилась в пользу России: турецкие войска были скоро отброшены за Кубань, восстание крымских татар подавлено, и в следующем 1783 году полуостров окончательно присоединен к России.
На юго-западном берегу Крыма, близ татарской деревни Ахтиар, у развалин древнего Херсонеса, находился обширный глубокий залив, в котором мог спокойно поместиться огромный флот, а небольшие бухты, вдающиеся из залива в берег, представляли полное удобство для устройства при них адмиралтейства, верфи и других портовых сооружений. Значительная глубина этих бухт в некоторых местах давала возможность большим линейным кораблям подходить к самому берегу, а широкий проход представлял удобный при всех ветрах выход с рейда в море, круглый год не замерзающее. Укрепления, возведенные на береговых возвышениях, могли защищать рейд от нападения неприятеля, а прекрасный теплый климат и отсутствие болот служили ручательством за здоровое положение местности.
Все эти достоинства Ахтиарского залива были хорошо известны морскому начальству от офицеров, которым прежде случалось заходить на рейд, и потому в мае 1783 года контр-адмиралу Мекензи поручено было устройство здесь порта и города, названного Севастополем и впоследствии вполне оправдавшего свое имя, в переводе означающее «Знаменитый город».
На другой же год по основании Севастополя он сделан главным портом Черноморского флота, с которым слился и Азовский флот. По штату 1785 года положено в Черноморском флоте содержать два 80-пушечных и десять 66-пушечных кораблей, 20 фрегатов, 3 камели и достаточное число мелких, ластовых и транспортных судов. Общее число морских чинов полагалось 13Уз тысяч человек. Кроме собственно морских команд, в Херсон и Севастополь из разных губерний выслано было несколько сот рабочих, и в числе их из Петербурга 40 семейств охтенских плотников. Все необходимые для портов строительные и другие материалы и предметы доставлялись из разных, иногда весьма отдаленных мест, как например, лес, кроме Крыма и Воронежа, из Белоруссии и Польши, а железо с уральских заводов.