Площадь находится у северо-восточного склона Центрального городского холма, от нее начинаются две магистрали городского кольца — ул. Ленина и пр. Нахимова. Она является главной и старейшей площадью Севастополя, его историческим центрам.
          Первые каменные постройки на месте будущей площади были заложены 3 июня 1783 года: пристань (на месте Графской) и дом командующего эскадрой контр-адмирала Т. Мекензи.
          Д. Н. Сенявин писал: «Пристань сделана с небольшим в месяц, а в дом перешел адмирал и дал бал на новоселии 1 ноября».
          Постепенно город строился. Появились дома капитанов кораблей. Рядом с домом Мекензи стал дом капитана I ранга Тизделя, за ним еще два небольших домика, напротив них - длинное здание казармы. В казарме первоначально жили морские офицеры, потом она была превращена в адмиралтейские магазины, а в 1814 году — снесена.
          К югу от пристани, на берегу Южной бухты, расположилось адмиралтейство, огражденное вначале деревянной решеткой, а потом - каменной стенкой.
          От площади начиналась первая улица города - Балаклавская дорога, позднее — Адмиралтейская, Екатерининская (ныне ул. Ленина).
          В 1787 году Севастополь посетила императрица Екатерина II. 22 мая она прибыла в Инкерман, а оттуда через бухту на катере, в сопровождении гребных судов, отправилась в Севастополь. Катер подошел к пристани (нынешней Графской), откуда императрица прошла в специально приготовленный для нее дом (бывший дом Мекензи), который после этого стал называться «Екатерининским дворцом», а площадь и пристань получили наименование «Екатерининских».
          В начале XIX века к северо-западу от Екатерининского дворца находился казенный дом в пять окон по фасаду, в котором жил начальник гарнизонной артиллерии, за домом тянулся ряд длинных флигелей — казармы нижних чинов гарнизонной артиллерии. У подножия Центрального городского холма стояло здание гауптвахты. В западной части площади была возвышенность, через которую шла дорога на ул. Б. Морскую.
          Благоустройство площади связано с именем М. П. Лазарева, главного командира Черноморского флота в 1834 - 1851 годах. В 1838 году в одном из писем Лазарев так описал площадь: «Голая и неправильная площадь, на которой разбросаны безобразные строения по произволу!» М. П. Лазарев приложил много усилий для того, чтобы изменить облик площади, украсить ее.
          В 1837 - 1846 годах была перестроена Екатерининская (Графская) пристань: ее удлинили, построили два караульных домика и колоннаду. В 1847 году на месте гауптвахты был построен Дом общего собрания флагманов и капитанов. М. П. Лазарев сам выбрал это место для строительства здания и внимательно следил за его ходом. Сооруженный в классическом стиле дом стал украшением площади.
          В середине XIX века Екатерининская площадь изменила свой облик. Она была чистой, вымощенной, служила местом прогулок жителей города, вечером на площади играла музыка.
          С площади открывался вид на Центральный городской холм, где был разбит общественный - сад Морского ведомства (позднее Мичманский, ныне Матросский бульвар). На бульваре возвышался памятник Казарскому, беседка в мавританском стиле.
          С северо-западной стороны на площадь выходила Николаевская батарея, строительство которой было окончено в 1844 году. Батарея была трехъярусной казематированной, длина по наружному фасаду - около 470 м. К началу первой обороны она имела на вооружении 105 орудий.
          Во время первой обороны Севастополя площадь стала оживленным местом, так как с Графской пристани осуществлялось снабжение бастионов снаряжением и продовольствием, поддерживалась связь с Северной стороной. Л. Н. Толстой так описывал пристань и площадь в «Севастопольских рассказах»: «На набережной шумно шевелятся толпы серых солдат, черных матросов и пестрых женщин. Бабы продают булки, русские мужики с самоварами кричат: сбитень горячий и тут на первых ступенях валяются ядра, бомбы, картечи и чугунные пушки разных калибров. Немного далее большая площадь, на которой валяются какие-то огромные брусья, пушечные станки, спящие солдаты, стоят лошади, повозки, зеленые орудия и ящики, пехотные козлы; двигаются солдаты, матросы, офицеры, женщины, дети, купцы; ездят телеги с сеном, с кулями и бочками; кое-где проедет казак и офицер верхом, генерал на дрожках. Направо улица загорожена баррикадой. Налево красивый дом с римскими цифрами на фронтоне, под которым стоят солдаты и окровавленные носилки, - везде вы видите неприятные следы военного лагеря».
          В последние дни обороны здание собрания было разрушено, Екатерининский дворец сильно поврежден. Графская пристань пострадала от взрыва баржи с порохом. Николаевская батарея была взорвана французами осенью 1855 года.
          После Крымской войны, в конце 1860-х - начале 1870-х годов, площадь благоустраивается. Была реставрирована Графская пристань, восстановлен Екатерининский дворец. В 1885 году на территории разрушенной Николаевской батареи разбили Приморский бульвар. В 1887 году на месте Дома общего собрания флагманов и капитанов было построено здание Морского собрания.
          На Екатерининской площади находилась одна из лучших гостиниц города — гостиница Киста.
          Облик площади формировало также трехэтажное здание гостиницы «Гранд-отель» (ул. Екатерининская, 1). Владельцем гостиницы в начале XX века был Л. Д. Кидонис.
          18 ноября 1898 года, в 45-ю годовщину Синопского сражения, на площади был открыт памятник П. С. Нахимову.
          На площади перед Морским собранием, на месте, отведенном для сооружения памятника, в 1890-е годы находились небольшой сквер и, фонтан. Морское ведомство выделило средства, необходимые для того, чтобы убрать их. Открытие памятника Нахимову было важным событием в жизни города. Газета «Крымский вестник» часто информировала читателей о ходе работ по сооружению памятника. Так, в номере от 31 октября 1898 года сообщалось: «Работы по установке памятника Нахимову быстро продвигаются к окончанию. Все гранитные работы окончены, статуя адмирала высится на пьедестале. Идут работы по установке орнаментов».
          Памятник был открыт в торжественной обстановке, в присутствии императора Николая II. На открытие были приглашены участники Синопского боя и обороны Севастополя 1854 — 1855 годов, родственники адмирала П. С. Нахимова. На площади соорудили павильон для высочайших особ, трибуны для публики. У памятника состоялся парад войск, играл оркестр.
          В конце XIX — начале XX века Екатерининская площадь являлась главной и самой красивой площадью города. Она была замощена освещалась электричеством. Здесь не было магазинов, мастерских, жилых домов, располагались только общественные здания и гостиницы. Площадь служила местом прогулок жителей и гостей города.
          Выполняла площадь и транспортную функцию. Южнее Графской пристани, на месте современного Морского вокзала, находились пристань и агентство Русского общества пароходства и торговли. Пароходы РОПиТ совершали пассажирские рейсы в Одессу, порты Крыма и Кавказа.
          К северу от Графской пристани располагались яличная пристань и пристань городского пароходства для сообщения с Северной и Корабельной сторонами. Паровые катера перевозили пассажиров по линиям Графская — Павловский мыс и Графская - Северная.
          На площади у Графской пристани имелась стоянка извозчиков.
          В сентябре 1898 года в Севастополе было открыто трамвайное движение. Через Екатерининскую площадь проходила круговая линия трамвая, а от площади начиналась Артиллерийская линия (по Нахимовскому пр., через Корниловскую и Базарную площади и Артиллерийскую слободку на Б. Морскую).
          Екатерининская плошадь — свидетель многих событий истории города.
          8 мая 1917 года в Севастополе происходило перезахоронение останков руководителей Севастопольского ноябрьского (1905 года) вооруженного восстания П. П. Шмидта, Н. Г. Антоненко, А. И. Гладкова. С. П. Частника, расстрелянных в 1906 году на о. Березань. Крейсер «Принцесса Мария» с останками революционеров подошел к Графской пристани. При входе крейсера в бухту с кораблей флота был произведен салют, а на берегу и у пристани собрались тысячные толпы народа, военно-морские части и организации со знаменами. На Графской пристани была отслужена панихида. Траурное шествие от пристани по Нахимовскому пр. и Б. Морской двинулось к Покровскому собору, в склепы которого были помещены останки революционеров.
          После 1917 года площадь неоднократно переименовывалась: в 1920-е годы она называлась пл. Труда, Красной пл., с мая 1928 года — пл. III Интернационала, в 1946 — 1951 голах — пл. Парадов, затем пл. Ленина и в 1957 году названа именем П. С. Нахимова.