Проектирование и выбор мест для новых городов были полностью предоставлены власти Г.А. Потемкина, который лично, несмотря на свирепствовавшую эпидемию, сразу после присоединения, осмотрел Крым с этой целью. В результате Потемкин представил Екатерине II свое мнение о крепостях в Тавриде, которое получило высочайшую апробацию.

Под свою особую опеку Потемкин взял строительство Севастополя (в переводе с греческого – город величественный, почтенный, достойный поклонения), как базы для молодого, созданного им Черноморского флота. Предназначение и весь смысл существования Севастополя – это корабли и море, ведь строился он именно как военный порт Российской империи на Черном море. В боях Севастополь заслужил гордое звание города русской военной славы.  

На юго-западном берегу Крымского полуострова, близ татарской деревушки Ахтияр, у развалин древнего Херсонеса, находился обширный глубокий залив, в котором мог спокойно поместиться огромный флот, а небольшие бухты, вдающиеся из залива в берег, представляли полное удобство для устройства при них адмиралтейства, верфи и других портовых сооружений. План Ахтиярской гавани с указанием древних городов Ахтиара и Херсонеса, постов российской армии был составлен еще в 1772 г. премьер-майором С. Бурнашевым. Значительная глубина этих бухт представляла возможность большим линейным кораблям подходить к самому берегу, а широкий проход давал удобный при всех ветрах выход с рейда в море, круглый год не замерзающее. Укрепления, возведенные на береговых возвышениях, могли защищать рейд от нападения неприятеля, а прекрасный теплый климат и отсутствие болот свидетельствовали о здоровом положении местности.

К середине XVIII в. на территории вокруг будущего Севастополя имелись лишь монастырь и села Инкерман и Ахтияр. По имени последнего иногда называли самую большую бухту. Военно-стратегическое значение этого места еще до присоединения Крыма привлекло внимание русских моряков, которые в 1782 г. сделали первый промер глубин. Екатерина II писала в это время Г.А. Потемкину: «Присоединение сея гавани поставляем Мы выше всякого сомнения или спора с чьей бы то стороны не было».

Потемкин уделял строительству Севастополя особое внимание, и 10 февраля 1784 г. был издан указ об основании военного порта с верфями, портом и военным поселением. Севастопольская крепость должна была быть «со внутренним строением, Адмиралтейством, морскими магазеинами, с каменною плотиной и с тремя отдельными зданиями». Особое значение приобрел город в период русско-турецкой войны 1787–1791 гг. В 1786 г. был составлен план работ по строительству Севастополя, рассчитанный на 10 лет. После окончания войны Севастополь превратился в один из крупнейших городов Крыма. В 1792 г. здесь проживали 15 тыс. человек. Сохранились документы о греках, желающих переселиться из Архипелага в Таврическую область, об учреждении для них народных школ и училищ; списки переселенцев и греческих чиновников, просящих об отводе земли вокруг Севастополя и Балаклавы.

Труды основателей и строителей города увенчались скорым успехом, спус­тя всего двадцать лет после основания – 23 февраля 1804 г. указом Александра I Севастополь был назначен «главным военным портом» России на Чер­ном море, а купеческим кораблям разрешалось заходить в него только во время шторма или поломки.