Под свою особую опеку взял Потемкин строительство Севастополя (в переводе с греческого — величественный город), считая его базой для молодого, созданного им Черноморского флота. К середине XVIII в. на территории вокруг будущего Севастополя, у развалин древнего Херсонеса Таврического, имелись лишь монастырь и села Инкерман и Ахтияр. По имени последнего иногда называли самую огромную бухту. Военно-стратегическое значение этого места еще до присоединения Крыма привлекло внимание русских моряков, которые в 1782 г. сделали первый промер глубин. Обширный глубокий залив, где мог спокойно поместиться огромный флот, небольшие бухты, вдающиеся в берег, представляли полное удобство для устройства при них адмиралтейства, верфи и других портовых сооружений, а широкий проход давал удобный при всех ветрах выход с рейда в море, круглый год не замерзающее. Екатерина писала в это время Потемкину: «Присоединение сея гавани поставляем Мы выше всякого сомнения или спора с чьей бы то стороны не было». Со времен Петра Великого Россия стремилась закрепиться на Черном море. Задача потребовала жертв и усилий нескольких поколений.
После того как Крым был «принят под державу Всероссийскую», в апреле 1783 г., для защиты побережья на безлюдном берегу, где им предстояло построить город — славу России, расположился гренадерский батальон, а затем два полка. Командовавший Азовской флотилией вице-адмирал Ф.А. Клокачев, узнав о хороших качествах гаваней, прибыл с эскадрой и для стоянки выбрал Южную бухту. На ее берегах матросы начали строить жилые дома и склады. Но вскоре Клокачев уехал, и его место занял контр-адмирал Ф.Ф. Мекензи. 2 июля 1783 г. он писал графу И.Г. Чернышеву: «Ныне мы упражняемся в Ахтиарской гавани — делаем казармы, магазины; также завел уже маленькое адмиралтейство». Кроме адмиралтейства Ф.Ф. Мекензи заложил часовню во имя Св. Николая Чудотворца, дом для себя и пристань. Неподалеку от них возвели небольшие дома для офицеров, столовые и кухни для экипажей. Кроме того, было устроено «два хороших тротуара, один от пристани до крыльца дома адмиральского, а другой от дома до часовни, и обсажены деревьями. Выстроено шесть красных лавок с жилыми наверху покоями, один изрядный трактир, несколько лавок маркитанских, три капитанских дома, несколько магазейнов и шлюпочный сарай в адмиралтействе: все строения каменные или досчатые. Итак, — как писал Мекензи, — весной 1784 г. все строения Севастополя были оштукатурены, выбелены, хорошо подкрашены палевой или серой краской, крыши на всех черепичные, и все вместе на покатости берега делает вид очень хороший».
Руководил строительством сам Г.А. Потемкин, присылавший подробные ордера с конкретными указаниями. Главная его мысль: «Севастополь должен быть силен укреплением». Это военно-морской порт. Камень для стройки в основном брали из развалин Херсонеса, несколько позже его стали добывать в Инкермане. 10 февраля 1784 г. указом Екатерины II «для обеспечения безопасности границ» было поведено устроить «крепость большую Севастополь, где ныне Ахтиар, и где должны быть Адмиралтейство, верфь для первого ранга кораблей, порт и военное поселение». Севастопольская крепость планировалась «со внутренним строением, Адмиралтейством, морскими магазинами, с каменною плотиной и с тремя отдельными зданиями». В память о монаршем попечении одна из центральных улиц города получила имя Екатерининской и носила его до разрушительного 1917 г.
Начиная с 1784 г. силами солдат возводились дороги, они связывали Севастополь с Бахчисараем и другими населенными пунктами Крыма, приводились в порядок каменные мосты через многочисленные реки и ручьи. В 1785–1786 гг. дороги были закончены и вдоль них установлены каменные знаки с обозначением миль и верст, изготовленные по рисункам, присланным от Потемкина. Одна из таких миль, в виде усеченной колонны на пьедестале, сохранилась до настоящего времени на Северной стороне города. Строительство города проходило под непосредственным руководством инженера Н.И. Корсакова. Был разработан план, в соответствии с которым в августе 1785 г. намечалось развернуть работы по сооружению крепости и адмиралтейства. В это же время был составлен проект Севастополя. Для новых кварталов предназначалась свободная территория между Артиллерийской и Карантинной гаванями.
Будучи опытным военным, Потемкин, самолично обозревший Ахтиярскую гавань, видел не только ее достоинства, но и возможные трудности в обеспечении обороны Севастополя в случае осады. С беспокойством сообщал он своей венценосной покровительнице, что при всех преимуществах местоположения города «надо захватить всю длину, которая содержит около трех верст, от чего крепость вышла необъятной окружности. Чрез глубокие там овраги очень трудно и почти невозможно соединить части крепости и так защитить себя, чтоб не открыть тылу некоторых линий и самой внутренности залива прямолинейному действию неприятельских орудий».
С 1786 г. Севастополь строился под руководством капитана, а затем вице-адмирала графа М.И. Войновича, назначенного на место умершего Ф.Ф. Мекензи. О состоянии города первых лет его жизни свидетельствуют записки «севастопольского старожила»: «Севастополь за три года со время основания до путешествия императрицы Екатерины II имел всех строений не более сорока, казенных и партикулярных; в порту не было еще никаких укреплений, и адмиралтейство только еще устраивалось…»
На низменном берегу в 1785 г. была возведена каменная лестница, названная Екатерининской пристанью. Со временем она получила название Графской, в честь графа Войновича. Слева от нее располагалась одноэтажная караульня, сохранившаяся до наших дней. Напротив лестницы размещались дома Мекензи и капитанов; они имели один этаж и простые формы. С другой стороны площади находилась офицерская казарма, от нее начиналась обсаженная тополями, сливами и вишнями Балаклавская дорога. Вдоль нее располагалось несколько жилых строений и Николаевская церковь, отличавшаяся гармоничностью и стройностью пропорций.
В 1787 г. императрица Екатерина II посетила Севастополь, где ей и сопровождавшим ее послам был представлен созданный Г.А. Потемкиным Черноморский флот, с 13 августа 1785 г. находившийся в его подчинении. Снаряжала его вся Российская империя: суда строились на Воронежской верфи, Белоруссия, кроме кораблей, обеспечивала черноморцев парусиной, канатами, сукном для обмундирования, тульские и уральские оружейники трудились над изготовлением артиллерии и оружия для кораблей, помимо морских команд, в Севастополь из разных губерний было выслано несколько сот рабочих, в их числе из Петербурга 40 семейств охтинских плотников. Большую помощь оказали балтийские моряки: в новый военный порт были направлены корабли Балтийского флота, а офицерами и матросами с Балтики комплектовали экипажи Черноморского флота. К сожалению, в первые дни войны Севастопольский флот попал в жестокий шторм и был рассеян; его потеря искренне огорчила и Потемкина, и Екатерину, но светлейший приложил все усилия для восстановления Черноморской эскадры.
Заботясь о создании сильного флота, Потемкин вкладывал даже личные средства в строительство кораблей, используя ресурсы своих белорусских имений. Верфи были построены в селе Дорогокупове на реке Двине, в Полоцком наместничестве и в городе Кричеве, где также располагалась парусная фабрика и канатный завод, работающие на нужды флота. В Дорогокупове строились военные корабли — «канонерские лодки с одним на носу двенадцатифунтовым единорогом» и десантные суда, где «помещалось с гребцами по осемнадцати человек», а в случае надобности «можно было поставить на носу трехфунтовую пушку». В Велиже (согласно ведомости по Полоцкому наместничеству) суда строились «близ самого города Велижа при реке Двине, остродонные, называемые волны, разных мер по древнему заведению обычаем… в Крическом старостве купеческие суда, называемые бандаки, кои поднимают по 5 и 10 тысяч пуд». Делали корабли крестьяне князя Г.А. Потемкина, а отправляли их от местечка Кричева рекою Сожем, «а из оной Днепром в город Херсон с пенькой и канатами, а оттоль, — как сказано в документе, — возвращаются с крымской солью».