В 1827 году по приказу вице-адмирала Грейга в Херсонесе были произведены раскопки, целью которых было подтвердить или опровергнуть предание о том, что именно здесь была та самая церковь, в которой крестился св. кн. Владимир. После того, как на предполагаемом месте были найдены остатки древней базилики с крестильным храмом, Грейг обратился к государю с предложением выстроить здесь «небольшую изящной архитектуры церковь».
Высочайше одобренный доклад был передан в Академию художеств, объявившую конкурс на создание проекта памятника. Была начата и подписка по сбору средств.
Чести возводить храм удостоился знаменитый архитектор К. Тон, представивший лучший проект.
Прославленный адмирал М. Лазарев испросил у государя позволения воздвигнуть храм не в Херсонесе, а в Севастополе, где он чаще мог быть посещаем, «нежели за несколько верст от города». Одобрив эту мысль, император сам выбрал место для будущего строительства. Лазарев же заказал в Италии мрамор, деревянный иконостас... Но тут, к несчастью, тяжелая болезнь оборвала его жизнь. Похоронить адмирала решили в склепе на территории, выбранной под строительство собора. Над спешным возведением склепа днем и ночью работало более 200 человек, и к прибытию из Николаева парохода с телом Лазарева он был закончен...
Закладку храма производили позднее и до начала высадки неприятеля в Крыму в сентябре 1854 года успели построить лишь подвальный этаж. Предчувствуя гибель, ближайшие ученики Лазарева Корнилов и Нахимов выразили желание быть похороненными рядом со своим любимым наставником.
Первым хоронили адмирала Корнилова, геройски погибшего уже в октябрьскую бомбардировку. В начале марта следующего года отдаст свою жизнь за Севастополь адмирал Истомин. В память о его беспримерном подвиге Нахимов уступит ему выбранное уже место в склепе. Трудно было разместить еще одно тело, и, сознавая это, Нахимов все же не откажется от заветной мысли. «Лягу хоть в ногах у своих товарищей», — скажет он на похоронах Истомина. Его очень скоро и положат на том месте, где он стоял при погребении друга. Так все они и собрались вместе на священной для каждого русского земле, чтобы уже никогда более не расставаться...
Строительство самого собора завершали уже после Крымской войны, и продолжалось оно достаточно долго. Освящение собора состоялось 5 октября 1888 года и проходило в присутствии многих тысяч человек, в том числе участников обороны города, приехавших в Севастополь за казенный счет. Указом Александра III имена севастопольских героев были увековечены на мраморных плитах, расположенных на стенах храма.
С этого времени каждый год 5 октября, в годовщину первой бомбардировки Севастополя, в храме Святого Владимира служили особо торжественные панихиды по убитым воинам, павшим при защите Севастополя, сопровождавшиеся орудийным салютом кораблей Черноморского флота…
После взятия Перекопа в 1920 году в Севастополе установилась Советская власть. Собор оставался действующим еще несколько лет и был закрыт лишь в 1932-году.
Переданный вначале Авиационному спортивному обществу под мастерские, позднее он был превращен в склад. В период обороны Севастополя 1941 года в соборе размещались госпиталь, бомбоубежище, корректировочный пост гвардейского артдивизиона. После войны не раз поднимался вопрос о дальнейшей судьбе собора, но никакие решения так и не были приняты.
Возрождение священного для каждого русского храма началось лишь в 1991 году. Сегодня собор восстановлен во всей своей былой красе. И вновь, как и прежде, молятся здесь о сохранении чести и славы Черноморского флота, о геройских защитниках великого Севастополя.