В мае 1778 г. 10 турецких судов под командованием ГаджиМегмета бросили якоря в Ахтиарской бухте (на месте будущего Севастополя). 7 июня высадившиеся на берег турки атаковали русский дозор и убили казака. Туда немедленно поскакал Суворов. Суворов первым делом потребовал у турецкого адмирала найти и наказать убийцу. В ожидании ответа генерал-поручик поехал осматривать Ахтиарскую бухту. Его внимание привлек сравнительно узкий вход в бухту. Там он приказал построить земляные укрепления для «приличной артиллерии».
Как и следовало ожидать, Гаджи-Мегмет прислал письмо с уверениями в дружбе, но наказывать виновных не собирался. Суворов не стал вступать в полемику с турком. А в ночь на 15 июня по обеим сторонам бухты шесть пехотных батальонов приступили к постройке укреплений. Поутру разъяренный Гаджи-Мегмет разглядывал в трубу укрепления русских, закрывавшие ему выход в море. Немедленно к Суворову был отправлен посыльный с письмом, где запрашивалось, зачем русским понадобилось строить столь мощные укрепления. Ответ Суворова не замедлил себя ждать: «Дружески получа ваше письмо, удивляюсь нечаянному вопросу, не разрушили ли мы обосторонней дружбы… к нарушению взаимного мира никаких намерений у нас нет, а напротив, все наше старание к тому одному устремлено, чтобы отвратить всякие на то неприязненные поползновения и чтоб запечатленное торжественными великих в свете государей обещаниями содружество сохранить свято. Итак, мой приятель, из сего ясно можете видеть мою искреннюю откровенность и что сумнение ваше выходит из действий вашей внутренности…».
Мало того, по всей бухте были расставлены многочисленные конные и пешие посты русских, которые под угрозой оружия не разрешали туркам высаживаться на берег. Офицерам это Суворов объяснил карантином против чумы, свирепствовавшей в Турции. Оставшись без воды, Гаджи-Мегмет приказал уходить в Синоп. Больше турецкие корабли здесь не появятся до 1918 г.
В апреле 1783 г. капитан 2-го ранга И. М. Берсенев на фрегате «Осторожный» осмотрел Ахтиарскую бухту и предложил создать там военно-морскую базу. 2 мая 1783 г. в Ахтиарскую бухту вошли пять фрегатов и восемь малых судов Азовской флотилии под командованием вице-адмирала Клокачева.
Через три дня Клокачев направил донесение морскому министру: «При самом входе в Ахтиярскую гавань дивился я хорошему ея с моря положению, а вошедши и осмотревши, могу сказать, что во всей Европе нет подобной сей гавани – положением, величиной и глубиной. Можно иметь в ней флот до ста линейных судов, по всему же тому сама природа устроила лиманы, что сами по себе отделены на разные гавани, то есть военную и купеческую… Ежели благоугодно будет иметь ея Императорскому Величеству в здешней гавани флот, то на подобном основании надобно будет завесть здесь порт, как в Кронштадте».
Русские матросы в июне 1783 г. заложили на пологом мысе между Южной и Артиллерийской бухтами каменный дом для адмирала, пристань, кузницу и часовню. В последующем мыс будет назван именем Святого Николая.
Через несколько недель на берегах Ахтиарской бухты появятся и первые русские поселенцы.
Для строительства домов, складов и береговых батарей матросы и поселенцы использовали в основном местные материалы. Так, камень брали по соседству – на развалинах Херсонеса, глину и песок добывали по балкам и берегам бухты, мелколесье и кустарник шли на изготовление жердей и плетей. Вскоре из Центральной России прибыли обозы с лесом, железом и другими материалами, необходимыми для строительства. Работали весьма споро, и уже 2 июля 1783 г. контр-адмирал Мекензи докладывал морскому министру, что построено небольшое Адмиралтейство, продолжается строительство казарм, складов, а в бухте начат ремонт кораблей.
10 февраля 1784 г. последовал рескрипт Екатерины II: «Нашему Генерал-фельдмаршалу, военной коллегии президенту, Екатеринославскому и Таврическому генерал-губернатору князю Потемкину… с распространением границ Империи Всероссийской необходимо… и обеспечение оных, назнача по удобностям новые крепости… Крепость большую Севастополь, где ныне Ахтиар и где должны быть Адмиралтейство, верфь для первого ранга кораблей, порт и военное селение…»
Севастополь быстро строился. В Артиллерийской бухте построили пристань и склады. Вокруг южной оконечности Южной бухты возник поселок купцов и ремесленников. В Крым и в Севастополь Потемкин привлекал все категории переселенцев – иностранцев, беглых крестьян, старообрядцев и т. д. Вспомним, что в те времена крестьяне не имели права покидать своих помещиков, а дворяне вовсе не жаждали ехать в Крым, даже когда Потемкин бесплатно раздавал там пустующие земли.
Матушка-императрица прекрасно знала и о беглых, и о раскольниках, но лишь в нескольких письмах к Потемкину, соглашаясь с его политикой, просила его не афишировать наличие таких переселенцев в Крыму.