Еще в войну 1768—1774 гг. на Днепре и его притоках Икорец и Хопер было основано несколько верфей — Икорецкая, Новохоперская и Гнильтонская (в устье Дона на его притоке Гнилая Тоня). Там были построены 11 «новоизобретенных» кораблей и 8 фрегатов, составивших ядро Азовской флотилии.
В апреле 1783 г. капитан 2 ранга И.М. Берсенев на фрегате «Осторожный» осмотрел Ахтиарскую бухту и предложил создать там военно-морскую базу. 2 мая 1783 г. в Ахтиарскую бухту вошли пять фрегатов и восемь малых судов Азовской флотилии под командованием вице-адмирала Клокачева.
Сразу же на берегах Ахтиарской бухты началось строительство офицерских домов, казарм для матросов и солдат. В августе освятили первую небольшую каменную церковь.
Было создано несколько новых береговых батарей, а построенные в 1778 г. Суворовым редуты значительно усилили.
10 февраля 1784 г. последовал рескрипт Екатерины II: «Нашему Генерал-фельдмаршалу, военной коллегии президенту, Екатеринославскому и Таврическому генерал-губернатору князю Потемкину… с распространением границ Империи Всероссийской необходимо… и обеспечение оных, назнача по удобностям новые крепости… Крепость большую Севастополь, где ныне Ахтиар и где должны быть Адмиралтейство, верфь для первого ранга кораблей, порт и военное селение…»
Севастополь быстро строился. В Артиллерийской бухте возвели пристань и склады. Вокруг южной оконечности Южной бухты возник поселок купцов и ремесленников. В Крым и в Севастополь Потемкин привлекал все категории переселенцев — иностранцев, беглых крестьян, старообрядцев и т. д. Вспомним, что в те времена крестьяне не имели права покидать своих помещиков, а дворяне вовсе не жаждали ехать в Крым, даже если Потемкин бесплатно раздавал там пустующие земли.
Матушка-императрица прекрасно знала и о беглых, и о раскольниках, но лишь в нескольких письмах к Потемкину, соглашаясь с его политикой, просила его не афишировать наличие таких переселенцев в Крыму.
Любопытна топонимика названий Севастопольской бухты. Так, в 1785 г. капитан 1 ранга Ф.Ф. Ушаков выбрал для своего корабля «Святой Павел* стоянку у безымянного мыса на восточном берегу Южной бухты. С тех пор мыс стал именоваться Павловским.
Знаменитая Графская пристань обязана своим названием графу Марку Ивановичу Войновичу. Капитан 1 ранга Войиович командовал эскадрой, базировавшейся на Севастополь, и каждый день в одно и то же время садился на причале в шлюпку и отправлялся на корабли. В честь приезда императрицы было решено назвать главную пристань города Екатерининской, но это название не прижилось, и пристань осталась Графской.