Так исторически сложилось, что в Севастополе два собора, освященных во имя святого князя Владимира. Идея о создании на Херсонесе храма в память крещения здесь князя Владимира принадлежала еще архиепископу Иннокентию. А в 1825 году главнокомандующий Черноморским флотом А.С. Грейг подал императору Александру I докладную записку о сооружении небольшого храма в византийском стиле и богадельни. Чтобы определить, где крестился князь Владимир, в Херсонесе в 1827 году мичман Н. Крузе начал проводить первые археологические раскопки. Деньги на строительство церкви собирали по подписке. Но в 1836 году император Николай I, уступив просьбе адмирала М.П. Лазарева, принял решение о строительстве Владимирского собора в городе Севастополе.

В 1852 году вопрос о строительстве собора на главной площади Херсонеса возник вновь, и даже был разработан новый проект, автором которого являлся архитектор Давид Иванович Гримм. Однако, помешала война. А 2 июля 1859 года проект храма утвердили, и 18 августа создали строительный комитет. Место для возведения собора предложил граф А.С. Уваров. Он же производил раскопки и обнаружил на месте бывшей главной площади города древнюю базилику, которая, по его мнению, была тем самым храмом Рождества Божией Матери, в котором в 988 году и крестился Великий князь Владимир.

23 августа 1861 года состоялась торжественная закладка нового собора в присутствии императора Александра II и его семьи. После молебна Александр II и Мария Александровна уложили золотые десятирублевые монеты на первые каменные блоки будущего храма. Царь пожертвовал деньги на колокол весом 11 пудов, который был отлит из меди. А великий князь Владимир Александрович стал ктитором (покровителем) соборного храма, 14 августа 1867 года он собственноручно заложил основание главного престола святого Владимира, водрузил мраморный крест для святых мощей и положил камень в стене горнего места. Возведение храма завершили в 1877 году.