Турецкие лазутчики в это время всячески провоцировали крымских татар на выступления и вооруженные вылазки против русских войск, но судьба Крыма была уже решена, и в 1783 году он полностью перешел во владения Российской империи, получив наименование Тавриды.
28 декабря 1783 года русский посланник в Константинополе Я. И. Булгаков получил подписанные Портой договоры, признававшие Тамань, Кубань российскими. В договоре Турция отказывалась от притязаний на Крым. Базы русского флота перемещались еще южнее, в центр Крымского полуострова. Пришло время Севастополя. В его судьбе свое веское слово сказал великий Суворов.
«Подобной гавани, — писал он, обращая внимание на удобство Ахтиярской бухты и возможность строительства морской крепости, — не только у здешнего полуострова, но и на всем Черном море другой не найдется, где бы флот лучше сохранен и служащие на оном удобнее и спокойнее помещены были».
«Описная партия» штурмана Ивана Батурина обследовала его в 1773 году.
В Херсоне строились новые небольшие фрегаты, русские корабли, отпугивая турецких лазутчиков и усмиряя мятежных мурз, несли постоянно крейсерскую службу вдоль побережья, приглядываясь к удобной бухте.
Поэтому не удивительно, что 17 ноября 1782 года в Ахтиярской бухте стал на зимовку с фрегатами «Храбрый» и «Осторожный» капитан 1-го ранга И. М. Одинцов. Это была первая зимовка русских судов в бухте.
«Начало же Черноморскому флоту, — пишется в книге „Краснознаменный Черноморский флот“, — следует считать май 1783 года. В Ахтиярскую бухту (по названию небольшого селения) 2-го мая прибыла эскадра Азовской флотилии под началом вице-адмирала Ф. К. Клокачева, а 7-го в бухту вошло одиннадцать кораблей Днепровской флотилии. С этого времени морские силы на юге России стали именоваться Черноморским флотом. В честь его основания в том же году была отлита медаль „Слава России“».
11 января 1783 года Адмиралтейств-коллегии был дан следующий указ: «Для командования заводимым флотом нашим на Черном и Азовском морях повелеваем тотчас отправить нашего вице-адмирала Клокачева… Адмиралтейств-коллегии долженствует по требованию его вице-адмирала подавать ему всякое зависящее от нея пособие». Вместе с ним были отправлены произведенные в контр-адмиралы Роберт Дугдаль и Фома Фомич Макензи. В начале марта последний осмотрел Таганрог, Керчь и оттуда с эскадрой прибыл 2 мая в Ахтиярскую бухту, откуда Макензи донес графу Чернышеву: «В сей бухте я нашел два фрегата под командой Одинцова и принял под свое командование». «При сем, — писал Макензи, — не премину я вашему сиятельству донести, что при самом входе в Ахтиярскую гавань дивился я хорошему ея с морю положению, а вошедши и осмотревши, могу сказать, что во всей Европе нет подобной сей гавани — положением, величиной и глубиной. Можно в ней иметь флот до ста линейных судов, по всему же тому сама природа такие устроила лиманы, что сами по себе отделены на разные гавани, то есть — военную и купеческую. Без собственного обозрения нельзя поверить, чтоб так сия гавань была хороша. Ныне я принялся аккуратно всю гавань и положение ее мест описывать, и коль скоро кончу, немедленно пришлю карту». И далее добавил: «Ежели благоугодно будет иметь ея Императорскому Величеству в здешней гавани флот, то на подобном основании надобно будет завесть здесь порт, как в Кронштадте».
Фома Макензи, по указанию Клокачева, находит из числа местных греков строителей, выбирает из команд мастеровых и приступает к строительству. Возводятся казармы, сараи, небольшие флигели для офицеров, помещения для больных, столовые и кухни для экипажей.
Он пишет Чернышеву 2 июля 1783 года: «Нынче мы укрепляемся в Ахтиярской гавани — делаем казармы, магазины; также уже завел маленькое Адмиралтейство… Не могу довольно расхвалить вашему сиятельству удобности Ахтиярской гавани».
Строительство порта, утверждение России шло здесь тяжело. Болезнь косила всех. Не пощадила она главного командира Черноморского флота Клокачева, еле выкарабкался из ее цепких лап капитан Козлянинов и уехал в Петербург. Что говорить о моряках, солдатах, рекрутах, плотниках, всех работных людях. Макензи пишет с тревогой Чернышеву, что он не спускает морские команды на берег, там уже умерло 500 человек егерей. «Я всего оного избегаю по спасению всего общества, оставил всех господ штаб — и обер-офицеров и служителей на судах, кроме тех, кои у печения хлебов и других надобностей… А притом и для покупки мяса… посылать некого (за оказавшейся в лежащих в близких расстояниях татарских деревнях, даже и в полках великой опасной болезни)».
Однако город строился. Один за одним к еще не выстроенным причалам подходили корабли.
В мае 1784 года Федора Федоровича Ушакова назначают командиром вновь построенного линейного корабля «Св. Павел», командиром другого линейного корабля «Слава Екатерины» стал граф Марк Иванович Войнович.