В 1843 году, с учреждением самостоятельной епархии на Северном Кавказе, возникла необходимость в создании архиерейской резиденции. Инициатором предоставления участка для строительства выступил ставропольский купец и благотворитель Игнатий Волобуев, на территории усадьбы которого была устроена домовая церковь. Первый епископ Кавказский и Черноморский Иеремия (Соловьёв) освятил её в честь Воздвижения Креста Господня.
В 1845 году для епископа были приобретены три смежные усадьбы в Кузнечном переулке (ныне улица Голенева), где обосновалась Крестовоздвиженская церковь. С течением времени храм расширялся: были пристроены два боковых придела — южный в честь священномученика Игнатия Богоносца и северный в честь преподобного Антония Печерского. С восточной стороны была сооружена полукруглая апсида для алтаря, а над зданием возвели купол. Рядом была построена каменная звонница с пятью колоколами, отлитыми на литейном заводе Куликиной.
В 1870 году церковь была перестроена по проекту губернского архитектора Петра Прозоровского. Временный иконостас был заменён на дубовый с позолотой. На территории храма были построены свечной завод, фруктовый сад и пруд, питающий Желобовский ручей. Также при храме действовали курсы псаломщиков.
