Владимирский собор расположен на Центральном городском холме, является архитектурной доминантой центра города. История собора началась в 1825 г., когда главный командир Черноморского флота и портов адмирал А.С. Грейг просил Высочайшего разрешения установить памятник на развалинах Херсонеса, где совершилось крещение кн. Владимира и откуда началось распространение православной веры на Руси.
          В 1829 г. был объявлен конкурс на создание памятника. Был утвержден проект архитектора К.А. Тона (1794 - 1881 гг.) - пятикупольный собор в русско-византийском стиле, сочетающем характерные элементы и формы древнерусской архитектуры с элементами и формами византийского зодчества. Первоначально храм во имя святого равноапостольного князя Владимира предполагалось возвести на территории Херсонеса, но в 1842 г., по ходатайству адмирала М.П.Лазарева, обеспокоенного недостаточным числом православных храмов в Севастополе, было принято решение о строительстве собора в центре города.
          Подготовительные работы начались в 1848 г. В 1851 г. умер адмирал М.П.Лазарев, главный командир Черноморского флота, и в память о его заслугах решено было похоронить его в специально сооруженном склепе на месте будущего собора. Закладка собора была произведена 15 июля 1854 г. Предполагалось построить собор за три года.
          Военные действия в Крыму и Севастополе в 1854 - 1855 гг. прервали строительные работы. До высадки неприятеля в Крыму успели построить подвальный этаж, возвышавшийся над землей на 60 - 90 см. Во время обороны Севастополя в склепе, где покоился прах адмирала М.П.Лазарева, были похоронены его ученики и сподвижники - адмиралы В.А. Корнилов, В.И. Истомин, П.С.Нахимов. Так еще не построенный собор стал усыпальницей адмиралов, памятником обороны Севастополя 1854 - 1855 гг.
          Так как война нанесла большой урон городу, строительство собора было возобновлено только в 1858 г. Первоначальный проект был изменен архитектором А.А. Авдеевым (1818 -1895 гг.) и утвержден в 1862 г. Вместо предполагаемого пятикупольного теперь строилось однокупольное сооружение с сохранением прежних размеров в чисто византийском архитектурном стиле. Нижний храм был освящен во имя святого Николая 5 октября 1881 г., верхний - во имя святого равноапостольного князя Владимира в 1888 г.
          Основание храма - в виде креста. Здание имеет шлемовидный купол и такие же шлемовидные покрытия над апсидами. Над западным входом - пристройка со звонницей, северный и южный фасады - одинаковые, увенчаны треугольными фронтонами, украшены колоннами из крымского диорита, полукружиями арок. С наружной стороны в облицовку стен южного и северного фасадов вмонтированы четыре плиты из черного мрамора с именами адмиралов М.П. Лазарева, В.А. Корнилова, П.С. Нахимова и В.И. Истомина и датами их смерти.
          Высота собора с крестом - 32,5 м; ширина - около 20 м, длина, с папертью и алтарем - 29 м. В облицовку стен верхнего храма были вмонтированы мраморные плиты с именами и фамилиями адмиралов и офицеров Морского ведомства, награжденных орденом св. Георгия за храбрость. Все работы по мрамору выполнены итальянским скульптором В. Бонани, орнаментовка - итальянским художником Р. Изелли, стены и своды расписаны художником А.Е. Карнеевым (1837 - 1896 гг.).
          Захоронение адмиралов М.П. Лазарева, В.А. Корнилова, В.И. Истомина, П.С. Нахимова в нижнем храме было отмечено черным мраморным крестом, на четырех сторонах которого были высечены бронзовые надписи с именами адмиралов и датами их смерти.
          С 1869 по 1920 гг. вдоль северного и южного фасадов были похоронены еще девять морских офицеров: П.А. Перелешин, П.А. Карпов, М.И. Дефабр, В.П. Шмидт, И.М. Ликов - участники обороны Севастополя 1854 - 1855 гг., С.П. Тыртов, Г.П. Чухнин, М.П. Саблин - командующие Черноморским флотом в к.XIX - н.XX вв., И.А. Шестаков - управляющий Морским министерством в 80-е годы XIX в.
          До 1917 года Владимирский собор содержался на средства Морского ведомства. В храме совершались только торжественные богослужения по воскресеньям, по церковным праздникам, в дни памятных событий первой обороны Севастополя, в дни тезоименитств членов императорской семьи. Церковная служба велась в соборе до 1932 года, когда договор с православной религиозной общиной был расторгнут, и церковь была закрыта. Здание передано в распоряжение авиационно-строительного общества под мастерские, позже в нем располагался склад политуправления Черноморского флота.
          В годы Великой Отечественной войны здание собора сильно пострадало. Реставрационно-восстановительные работы в храме начались в 1965 году. 6 марта 1972 года Владимирский собор стал филиалом Музея героической обороны и освобождения Севастополя, который проводит реставрационные работы в храме.
          19 октября 1992 года собор был вновь освящен, в нем проводится церковная служба.