Впервые памятник П.С. Нахимову появился 18 ноября 1898 года. Его открыли к 45-летию Синопского боя.
Памятник был отлит скульптором И.Н. Шредером, автор проекта — архитектор А.А. Бильдерлинг (генерал-лейтенант). В то время скульптура адмирала была развернута иначе — в сторону моря.
Первоначальный монумент просуществовал 30 лет, и в 1928 году, выполняя Декрет Советской власти «О снятии памятников царям и их слугам», его снесли как памятник «царскому адмиралу». На сохраненный постамент в 1932 году водрузили статую В.И. Ленина (скульптор В.В. Козлов), которая была, в свою очередь, осквернена фашистскими захватчиками.
5 ноября 1959 года справедливость, наконец, восторжествовала — на постамент воздвигнут новый памятник легендарному адмиралу, сделанный по старым чертежам народным художником СССР Н.В. Томским и архитектором А.В. Арефьевым. За создание памятника Н.В. Томский был удостоен Золотой медали Академии художеств СССР. В работе принимал участие архитектор М.3. Чесаков.
На сохранившемся профилированном основании, на гранитном пьедестале в виде усеченной пирамиды установлена бронзовая скульптура адмирала. Он изображен в полный рост, гордо поднятая голова слегка развернута влево, взгляд устремлен в сторону города. Одет в адмиральский мундир с эполетами, с которыми он не расставался под самым сильным огнем. У ворота видна почетная награда — Георгиевский крест. На голове — фуражка, на боку — палаш на перевязи. Левая рука заложена за спину, в правой — зрительная труба.
Новая скульптура почти идентична первоначальной. Отличаются только размеры (она немного выше) и направление взгляда адмирала. Общая высота памятника — 12,5 м (первого 10 м), высота фигуры — 5,33 м (первой 4 м).
Статуя поставлена таким образом, что П.С. Нахимов стоит лицом к городу и спиной к бухте и флоту. В свое время это было воспринято моряками с большой обидой, но со временем обида позабылась — ведь легендарный адмирал проявил себя не только великим флотоводцем, но и организатором сухопутной обороны Севастополя, а моряки под его командой сражались не только у берегов Синопа, но и на бастионах.
Прямоугольные выступы основания (с многочисленными выбоинами и сколами — следами войны) по углам монумента с лежащими якорями придают законченность всей композиции.
В нижней части пьедестала размещены три горельефа со сценами из жизни П.С. Нахимова — «Беседа с матросами», «Синопский бой», «Нахимов на четвертом бастионе».
На лицевой стороне постамента — бронзовое знамя, ниже на бронзовой плите отлит текст приказа адмирала: «В случае встречи с неприятелем, превышающим нас в силах, я атакую его, будучи совершенно уверен, что каждый из нас сделает свое дело». В этих словах - весь П.С. Нахимов: человек необычайного мужества, он свято верил в стойкость своих подчиненных. Этот текст почти без изменений перенесен со старого памятника. На тыльной стороне — бронзовый картуш с текстом: «Слава русскому флоту» в обрамлении воинских атрибутов. Выше в лавровом венке надпись о смертельном ранении адмирала 28 июня 1855 года на Малаховом кургане (Корниловском бастионе).
Памятник удачно вписывается в окружающее пространство, формирует главную площадь города. Расположение в центре площади дает возможность для детального осмотра монумента, его кругового обзора.