Вначале ознаменовать принятие киевским князем Владимиром крещения в Херсонесе было решено постройкой небольшой церкви византийского стиля. Идея эта принадлежала главному командиру Черноморского флота и портов вице-адмиралу А. С. Грейгу. Изложена она была в записке, поданной императору Александру I во время посещения им Севастополя.

При храме планировалась богадельня для увечных и неимущих, заботу которых должны были составить присмотр и за храмом, и за руинами древнего города. В 1827 г. по инициативе того же А.С. Грейга в Херсонесе были произведены раскопки трех храмов. Один из них, богато отделанный, стоящий на центральной площади, был принят за храм, в котором крестился киевский князь. В 1829 г. принято решение о начале всенародного сбора средств на сооружение храма - памятника крещению. Сбор средств осуществлялся долго. В 1843 году император Николай I указал другое место для возведения собора святого Владимира - в центре Севастополя на горе.

Строительные материалы и собранные деньги были разделены на две части, которые соответственно предназначались для возведения соборов святого Владимира в Севастополе и в Херсонесе, посвященных введению христианства на Руси. Собор в городе был заложен 15 июля 1854 г., когда корабли объединенной армады Англии, Франции и Турции уже появились на рейде Севастополя. Война, разрушившая и Севастополь, и монастырские строения в Херсонесе, надолго затормозила постройку храма. Сбор средств приостанавливался и объявлялся вновь в Таврической епархии и по всей России.

10 февраля 1858 г. Высочайшее разрешение на строительство храма наконец было подписано. Проект храма, составленный будущим ректором Академии Художеств академиком Д.И. Гриммом, был утвержден 2 июля 1859 года. 18 августа 1859 г. создан Строительный комитет. 23 августа 1861 г. императорская чета - Александр II и Мария Александровна, сопровождаемые большою свитою, после торжественного молебна, заложили первый камень храма. Но средств для строительства храма постоянно не хватало, и строительные работы растянулись на три десятилетия.

Первоначально смета составила 738 тыс. рублей и предусматривала отделку здания порфиром, мрамором и другими ценными породами камня. Замена порфира инкерманским камнем, использование балаклавских мраморовидных известняков, дали возможность уменьшить смету до 174 тыс. рублей. Многолетний долгострой, стремительно растущие цены на материалы и строительные работы уничтожили выигрыш в средствах от замены дорогих материалов на более дешевые: на строительство и отделку храма было затрачено 900 тыс. рублей.

Какие только стимулирующие меры не придумывались монастырем для продвижения строительства. После долгих переговоров согласился быть ктитором, покровителем храма Великий князь Владимир Александрович.

Однако личное участие ктитора, заложившего 14 августа 1867 г. первый камень верхней церкви, не предотвратило новой остановки строительных работ по старой причине недостатка средств. Наконец в 1877 г. постройка собора вчерне была завершена. До 900-летия крещения оставалось 11 лет. Десятилетие ушло на добывание средств на внутреннюю отделку. Эти работы удалось продолжить лишь в 1888 г. - на 300 тыс. р., выделенные из казны с выплатой по 100 тыс. каждый год.

Так как времени до праздника крещения оставалось мало, было принято разумное решение: не ухудшать качества внутренней отделки спешкой, к указанному дню освятить нижнюю церковь Рождества Богородицы, где провести торжественную литургию. Завершение всех внутренних работ осуществить в последующие три года. Но трех лет для отделки и внутренней росписи огромного храма было явно недостаточно, и завершение оформления в срок во многом определили высокая квалификация и организаторский талант главного руководителя работ академика Н.М. Чагина.

К выполнению проекта внутреннего оформления храма был привлечен коллектив талантливых художников и архитекторов. Художнику А.И. Корзухину, имевшему широкую известность, было поручено написание 72 икон. Росписи "Тайная вечеря", "Крещение Господне", "Священномученики Кирилл и Мефодий" (написана в память посещения ими Херсонеса в 861 году) были важнейшими в оформлении храма. Академик живописи П.Ф. Тихобразов, кроме оформления, разделял с Чагиным нелегкий труд организации работ, к которому были привлечены инженер-архитектор М.Ю. Арнольд и сын Н.М. Чагина Владимир. Академик В.И. Нефф, П.Т. Рисс и художник И.А. Майков осуществляли росписи стен храма. Талантливейшему художнику-самоучке крестьянину И.Т. Молокину была поручена реставрация пришедших в ветхость икон и роспись алтаря церкви южного притвора Александра Невского. Иконы эти были изготовлены для храма еще в 1849-1850 гг.

Перед Н.М. Чагиным стояло много сложностей из-за краткости сроков отделки храма, но он прекрасно вышел из затруднительного положения, организовав одновременную работу каждого из художников созданного им коллектива. В связи с этим все иконы, в том числе знаменитая "Тайная вечеря", писались А.И. Корзухиным не на лесах и подмостках под сводами, а в привычных условиях своей мастерской в Петербурге. Возможным это оказалось потому, что иконы и росписи делались на линолеуме, который затем накладывался на укрепленную на стене камышовую прокладку, предохраняя написанное от сырости каменной кладки.

Вспомним, сколько физических страданий и неудобств доставила Микеланджело роспись Сикстинской капеллы, когда ему приходилось лежать на лесах то на спине, то на боку, выписывая детали убранства капеллы. Остроумное решение Н.М. Чагина в значительной мере облегчило работу и улучшило ее качество. "Тайная вечеря" в алтарной части была одной из наиболее крупных росписей: около 9 м в длину при почти 5-ти метровой высоте. По свидетельству многих современников, по напряжению, динамичности изображений апостолов и выразительности корзухинская "Тайная вечеря" почиталась одной из лучших в России. Одновременно художник П.П. Прокофьев расписывал орнаментом стены храма, а итальянские мастера Сеппи и Баскерини у себя на родине в Серавессе близ острова Карары изготовляли мраморные части иконостаса, панели, кресты, чтобы в Херсонесе произвести только их окончательную обработку и подгонку. Мастера И.Т. Сафронов и И.А. Морозов выполняли бронзовые царские врата, изготавливали паникадила, лампады и фонари. В храме нижнего этажа деревянный резной иконостас, получивший широкую известность тонкостью и изяществом работы, выполнил придворный мастер Тихонов. Не уступал ему, а по мнению некоторых даже превосходил, ореховый иконостас в верхнем храме, изготовленный в мастерской Владимира Корецкого.

Высокие панели из карарского темно-пурпурного мрамора, красиво мерцавшего зелеными, синими и розовыми переливами, прикрывали нижнюю часть стен. Панели завершались светло-розовым карнизом. Арки окон первого яруса верхнего храма опирались на 54 колонны того же темного мрамора из Карары, выделяя галерею, которая шла вдоль трех фасадов. Темный мрамор колонн подчеркивал пленительную белизну мраморных баз и капителей строгого тонкого профиля. Высокие, стройных пропорций полуциркульные окна по форме перекликались с окнами настоятельского корпуса, стараясь, правда без особого успеха, объединить здания в один ансамбль. Железные рамы имели узорчатый переплет из кругов, который был характерен для византийской архитектуры. Несложный прием - стекла красного и желтого цвета - создавали в храме иллюзию пространства, пронизанного теплым солнечным светом в пасмурную погоду и смягчали резкость лучей в ясные, жаркие дни. Полы первого и второго этажей были выложены мозаикой белого, красного, желтого и черного цвета. Эта гамма была обычной для средневековых храмов Херсонеса. Сочетание декоративного оформления с торжественным убранством храма производило сильное впечатление.

Церковь первого этажа была темновата, но также богато убрана. Среди этой роскоши и благолепия вызывающе торчала грубая бутовая кладка древней церкви - основной святыни и причины собора. Ни тонкой работы иконостас, ни мраморные кресты с текстами об участии императорской семьи в строительстве собора, ни сверкающий мраморной белизной аналогий с мощами равноапостольного князя Владимира - ничто не могло скрасить грубости торчащих ребер бутовых скальных обломков, приглушить их вызов окружающему благолепию. И монастырь решил "причесать", "облагообразить" древнюю святыню. Неровно торчащие стены были разобраны до одного уровня и облицованы мрамором. В таком виде древняя кладка, по словам очевидцев, стала похожей на прилавок мясной лавки, по непонятной причине сохраненной внутри действующего храма.

Внешний вид собора также отличался монументальностью, торжественностью и величием. В плане это была трехнефная базилика, сочетающаяся с архитектурно подчеркнутыми формами крестово-купольного храма. Расположенный на главной площади древнего города, собор занимал почти всю ее величину и поражал своими размерами. На двадцатишестиметровой высоте отливала блеском цинковая черепица огромного купола. Основание храма подчеркивалось трехступенчатым цоколем из больших блоков светло-серого гаспринского мрамора. Замена в облицовке предусмотренного проектом порфира на плиты местного песчаника теплого желтоватого оттенка оказалась как нельзя более оправданной для зрительного восприятия здания, не допустив контраста с окружающими древними постройками. Акт приема строительных работ, подписанный академиком Д.И. Гриммом отмечал, что все части храма были выполнены из материалов превосходного качества, правильно, тщательно и прочно, с применением новейших требований строительной техники, так что вообще исполнение постройки не оставляет желать ничего лучшего и может считаться образцовым как в техническом, так и в художественном отношении.

Ко дню 900-летия крещения Руси при большом стечении народа был освящен нижний храм Рождества Богородицы. В октябре 1891 г. был освящен верхний соборный храм в честь Святого равноапостольного князя Владимира и еще годом позже, в 1892 г., храм в южном приделе - в честь Святого благоверного князя Александра Невского. Три десятилетия переживаний и трудных забот завершились.