Сразу же после присоединения Крыма к России (манифест Екатерины II «О принятии полуострова Крымского, острова Тамана и всей Кубанской стороны под Российскую державу» был издан 8 апреля 1783 года) на полуостров распоряжением императрицы был направлен фрегат «Осторожный» под командованием капитана II ранга Ивана Берсенева для выбора гавани у юго-западного побережья, на котором предполагалось построить стратегически необходимый военный порт. Осмотрев в апреле 1783 года бухту у поселка Ахтиар, расположенную неподалеку от развалин древнего города Херсонеса-Таврического, Берсенев рекомендовал ее в качестве базы для кораблей будущего Черноморского флота.
Датой основания современного Севастополя считается 14 июня 1783 года. В этот день под руководством контр-адмирала Мекензи были заложены первые четыре каменные постройки Севастополя: дом командующего Крымской эскадрой, часовня, кузница в Адмиралтействе и пристань, названная впоследствии Графской. Основателем города формально считается контр-адмирал шотландского происхождения Фома Фомич (Томас) Мекензи. Однако, справедливости ради, в этой связи нельзя не упомянуть Александра Суворова. Еще пятью годами ранее по его приказу на берегах нынешней Севастопольской бухты были построены первые земляные укрепления и размещены русские войска. Первоначально поселение называлось Ахтиар, по имени бывшей на месте города крымско-татарской деревни Ак-Яр (крымско-тат. белый берег, обрыв),
Современное название город получил 21 февраля 1784 года. В этот день Екатерина II своим указом повелела Григорию Потемкину устроить на его месте большую крепость и назвать Севастополем. Город строился на средства, полученные Потемкиным с новороссийских земель. Административно Севастополь вошел в состав Таврической области, образованной в составе Екатеринославского наместничества, центром которого являлся Екатеринослав (ныне Днепропетровск).
Название города состоит из двух греческих слов Σεβαστός (Севастос) — «высокочтимый, священный» и πόλη (полис) — «город». Севастос — эквивалент латинского титула «Август», поэтому название Севастополь можно перевести как «августейший город» или точнее — «императорский город». В советской литературе приводились переводы, по понятным причинам не связанные с императорским титулом. Так, например, в Большой советской энциклопедии название переведено как «величественный город», «город славы».
Реализацию первоначальной схемы строительства города взял на себя адмирал Федор Ушаков, назначенный в 1788 году командующим портом и Севастопольской эскадрой. Он построил много домов, казармы, госпиталь, дороги, рынки, колодцы.
Интересно, что в 1797 году император Павел I, который взойдя на престол многое сделал просто назло своей великой матери Екатерине, переименовал город-крепость в Ахтиар. Однако в 1826 году при Николае I сенатским указом городу было возвращено прежнее, греческое имя — Севастополь.
В 1830 году в Севастополе произошло крупное восстание, спровоцированное карантинными мерами во время русско-турецкой войны 1828—1829 годов. Так называемый «Чумной бунт» начался 3 июня и быстро вовлек в свои ряды матросов, солдат и городские низы. 4 июня восставшими был убит губернатор города Столыпин, несколько чиновников, и до 7 июня город находился в руках мятежников. После подавления восстания 1580 участников были преданы военному суду, семь из них — расстреляны.
Начало бурного роста Севастополя неразрывно связано с именем адмирала Лазарева. Назначенный начальником штаба Черноморского флота в 1832 году, а позднее — главнокомандующим флотом и военным губернатором города, он строит адмиралтейство с предприятиями судоремонта и судостроения на берегах Корабельной и Южной бухт. Создав таким образом производственную базу флота, Лазарев приступает к реконструкции и застройке города, для чего 25 октября 1840 года был разработан и принят первый генеральный план Севастополя. В частности, была снесена одноэтажная застройка Центрального холма, носившего название «Хребет беззакония», освободив место для зданий в духе классицизма. Одновременно, быстрее, чем в других городах Крыма, росло население Севастополя. По состоянию на 1850 год оно составляло 45 046 человек, из них 32 692 — нижние воинские чины. Дальнейшее развитие города было предусмотрено генеральным планом 1851 года, но его реализации помешала Крымская война 1853-1856 годов.
25 февраля (9 марта) 1855 года командиром Севастопольского порта и временным военным губернатором города назначен Павел Нахимов; в марте произведен в адмиралы. Нахимов энергично руководил обороной города и пользовался большим нравственным влиянием на солдат и матросов, звавших его «отцом-благодетелем». 28 июня (10 июля) 1855 года, во время одного из объездов передовых укреплений, был смертельно ранен пулей в голову на Малаховом кургане. Скончался 30 июня 1855 года. Похоронен в склепе Владимирского собора в Севастополе.
После долгой героической обороны Севастополя Крымская война 1854-56 гг завершилась его взятием. Город был зажжён, пороховые погреба взорваны, военные суда, стоявшие в бухте, затоплены, Севастополь представлял собой дымящиеся развалины.
По итогам Крымской войны Россия на два с лишним десятилетия потеряла право держать военный флот на Черном море. Это был период упадка Севастополя, в это время центр экономической и общественной жизни Крыма был перенесен в Симферополь. Однако затем флот был восстановлен и Севастополь снова стал военно-морской базой. Более того, в 1890 г. город, который с 1804 года считался главным торговым портом Российской империи на Черном море, был официально причислен к разряду крепостей, а торговый порт был перенесен в Феодосию.
