В 1825 году главнокомандующий Черноморским флотом А. С. Грейг подал императору Александру I докладную записку о сооружении небольшого храма в византийском стиле и богадельни в Херсонесе. В 1827 году мичман Н. Крузе начал проводить здесь первые археологические раскопки, чтобы точно определить, где же принял Таинство Крещения святой равноапостольный князь Владимир. Но в 1836 году император Николай I, уступив просьбе адмирала М. П. Лазарева, принял решение о строительстве собора в честь святого князя Владимира в Севастополе.
Лишь спустя 16 лет, в 1852 году, вопрос о строительстве Владимирского собора на главной площади Херсонеса возник снова. С целью сохранения святых мест России участок с развалинами Херсонеса, по ходатайству святителя Иннокентия, архиепископа Херсонского и Таврического, был передан из морского ведомства в епархиальное.
На месте крещения святого равноапостольного князя Владимира в Херсонесе начал создаваться Херсонесский монастырь. Сначала работами по созиданию новой крымской обители руководил настоятель Свято-Успенского Бахчисарайского монастыря архимандрит Поликарп. Но весь основной труд лег на плечи первого настоятеля Херсонесского монастыря — игумена Василия (Юдина), выходца из донских казаков.
На пожертвованные благотворителями средства и личные сбережения игумен Василий за два с половиной года построил небольшой каменный храм и два скромных помещения для монахов. 23 февраля 1853 года церковь была освящена в честь святой равноапостольной княгини Ольги. Кроме того, к тому времени под руководством члена Одесского общества истории и древностей Н. Мурзакевича был составлен проект храма в честь святого равноапостольного князя Владимира. Но этот проект осуществить не удалось.
Мирная жизнь Херсонесского монастыря была прервана Крымской войной 1853-1856 гг. На территории обители французы установили свою батарею и разместили пороховые склады, а земля была перерыта окопами. В ходе боевых действий первый храм и кельи были полностью разрушены.
После окончания войны игумен Василий отправился собирать пожертвования на восстановление Херсонесского монастыря на Дон, но в 1856 году он трагически погиб, переправляясь через реку. Новым настоятелем обители был назначен иеромонах Евгений (Экштейн), а с апреля 1857 года — игумен Анфим (Казимиров). 30 апреля 1857 года в Херсонесском монастыре освятили скромный деревянный храм в честь семи святых херсонесских епископов-мучеников. Эта церковь и новые монастырские кельи были построены на средства севастопольских купцов Петра и Михаила Телятниковых.
Через три года на месте деревянного храма был воздвигнут каменный, который 2 апреля 1861 года освятил архиепископ Таврический и Симферопольский Алексий. В этом храме в небольшом ковчеге хранилась частица мощей святого равноапостольного князя Владимира, переданная для Херсонесской обители императором Александром II из малой церкви Зимнего дворца. На ковчеге была надпись: «Десницею Всевышнего укреплен, идольскую прелесть отринул еси, славне, и святым Крещением просветятся, светом познания Христова Землю Русскую озарил еси».
С 1857 года, по повелению императора, ежегодно 15 июля (28 июля по н. ст.), в день памяти святого равноапостольного князя Владимира, из севастопольского адмиралтейского собора в монастырь стал совершаться Крестный ход. А 10 февраля 1858 года было получено высочайшее разрешение на строительство в Херсонесе соборного храма в честь святого князя Владимира. Проект храма, автором которого был Д. И. Гримм, утвердили 2 июля 1859 года.
К тому времени граф А. С. Уваров провел в Херсонесе раскопки, в ходе которых на месте бывшей главной площади города обнаружили древнюю базилику. По мнению графа, она и была храмом Рождества Пресвятой Богородицы, в котором в 988 году принял Таинство Крещения князь Владимир. Именно это место и было предложено для строительства будущего собора.
Елена Иванова