Строительство собора связано с увековечением крещения великого князя Владимира в 988 г. в Херсонесе. Проект собора разработал архитектор К.А. Тон, храм предполагалось построить на территории Херсонеса. В 1842 г. адмирал М.П. Лазарев обратился к императору Николаю I с просьбой разрешить воздвигнуть здание собора не в Херсонесе, а на вершине Городского холма Севастополя. Работы начались в 1848 г., однако военные действия под Севастополем в 1854 г. остановили строительные работы.
История распорядилась так, что Владимирский собор стал местом захоронения выдающихся адмиралов Российского флота. В 1851 г. на месте будущего храма в специально построенном склепе, был похоронен адмирал М.П. Лазарев. Во время обороны Севастополя 1854–1855 гг. в этом же склепе были погребены сподвижники Лазарева – адмиралы В.А. Корнилов, В.И. Истомин, П.С. Нахимов, погибшие на бастионах Севастополя.
Строительство собора возобновилось в 1858 г. Проект К.А. Тона был переработан архитектором А.А. Авдеевым. С 1869 по 1920 гг. в соборе похоронены еще 9 военно-морских деятелей России: контр-адмирал П.А. Карпов (1822–1869), адмирал П.А. Перелешин (1821–1901) адмирал И.А. Шестаков (1820–1888), адмирал С.П. Тыртов (1839–1903), вице-адмирал Г.П. Чухнин (1848–1906), адмирал В.П. Шмидт (1827–1909), вице-адмирал И.И. Дефабр (1827–1910), адмирал И.М. Диков (1833–1914), вице-адмирал М.П. Саблин (1869–1920). Всего в храме похоронено тринадцать адмиралов.
Собор Св. Равноапостольного князя Владимира закладывался как памятник крестителю Руси, но в ходе строительства он стал и памятником героям Крымской войны 1853–1856 гг. и обороны Севастополя 1854–1855 гг., освящен 17 октября 1888 г.
В 1932 г. собор был закрыт, впоследствии в нем размещались мастерские, складские помещения. Во время Великой Отечественной войны храм сильно пострадал. В 1965 г. принято решение о восстановлении собора. В 1973 г. здание передали Музею героической обороны и освобождения Севастополя.
20 октября 1991 г. собор вновь освящен, возобновлено богослужение. Значительным событием стало перезахоронение 29 февраля 1992 г. праха адмиралов М.П. Лазарева, В.А. Корнилова, В.И. Истомина, П.С. Нахимова и восстановление крестообразного надгробия усыпальницы.
Комплексная реставрация Владимирского собора была проведена на средства Министерства обороны Российской Федерации в 2011–2014 гг. К жизни вернули фрески и орнаментировку стен и сводов, укрепили фундамент здания, восстановили памятные доски с именами адмиралов, отреставрировали крест над куполом храма. На звоннице собора были установлены 10 колоколов, отлитых в г. Тутаев Ярославской области.
Традиции морского храма продолжают жить. В соборе были освящены Андреевские флаги и вымпелы кораблей, ежегодно совершается молебен в честь основания Черноморского флота, проходят богослужения и панихиды по морякам, погибшим в годы первой (1854–1855) и второй (1941–1942) оборон Севастополя; в память о подвиге моряков крейсера «Варяг», по морякам подводной лодки «Курск».
