Дворцовая церковь Воздвижения Честного и Животворящего Креста была построена по желанию Императрицы Марии Александровны – супруги Императора Александра II.
Закладка фундамента храма состоялась 8 (21) сентября 1862 г. по проекту архитектора Высочайшего Двора Ипполита Антоновича Монигетти (1819–1878). 20 августа 1866 г. храм был освящен. Ранее Императрица согласовала со Святейшим Синодом название храма. Из всех особо почитаемых православных двунадесятых праздников она выбрала Воздвижение Креста Господня, отмечаемого 14 (27) сентября – месяца, который собиралась проводить в Крыму.
Современники отметили удачно найденные пропорции здания, изящную простоту, гармоничное сочетание византийского стиля с элементами архитектурных традиций православных храмов Закавказья. В художественном оформлении храма принимали участие многие известные русские и итальянские художники, скульпторы, мозаичисты.
В апреле 1887 г. рядом с дворцовой церковью по проекту Д. И. Гримма началось строительство звонницы с шестью колоколами, в византийском стиле. В 1910–1911 гг. церковь была частично перестроена архитектором Николаем Петровичем Красновым при строительстве нового Большого Дворца для Императора Николая II и его семьи.
21 октября 1894 г. в Крестовоздвиженской церкви была проведена панихида по Императору Александру III, скончавшемуся в Малом Ливадийском Дворце. Там же был обнародован Манифест о вступлении на престол Императора Николая II, затем состоялась церемония принятия православия невестой Цесаревича Алисой-Викторией-Еленой-Луизой-Беатрисой, дочерью великого герцога Гессенского Людвига IV, английской принцессы Алисы. Будущая Императрица была наречена именем Александра Федоровна.