История церкви Воздвижения Креста Господня (Крестовоздвиженского храма) уходит своими корнями в середину XIX века, когда в 1825 году к северу от Кисловодской слободы и источника Нарзан возникла казачья станица, основанная поселившимися на Северном Кавказе запорожскими и донскими казаками, защищавшими южные границы России. Они же возвели небольшую церковь с колокольней, освящённую в честь Воздвижения Креста Господня.
Станица росла, население её увеличивалось. В 1895 году общество станицы Кисловодской обратилось с ходатайством к Преосвященнейшему Владимиру, Епископу Владикавказскому и Моздокскому, о расширении церкви и строительстве новой колокольни, больших размеров.
В 1896 году благословение было получено, и начался сбор пожертвований. Сборная книга на постройку храма была выдана на имя казака Елиазара Матвеевича Нагорного и крестьянина Евдокима Михайловича Докукина. Руководил работами приходской священник Михаил Лисицын. Реконструкция шла довольно долго и окончательно была завершена в 1906 году. Однако в годы советского богоборчества храм был уничтожен.
В 1964 году после разрушения Пантелеимоновского храма в городе Кисловодске церковные службы проводились в небольшом деревянном бараке.
В здании, отданном под церковь, размещались классы школы, общей площадью 10х10 м. С разрешения горисполкома полезную площадь расширили ещё на 6 кв. метров. Но со временем прихожан становилось больше, что требовало строительства более просторного храма.
Разрешение на строительство было получено через 10 лет. Документов разрушенного храма не сохранилось, поэтому было решено выбрать традиционный для православной архитектуры тип храма. Строительство проводилось в тяжелых условиях. Однако несмотря на препятствия со стороны властей, стройка была всенародной. Средства поступали со всей страны, каждый старался положить кирпичик в стены нового храма.
В начале 80-х годов. ХХ века туристам из зарубежных стран рассказывали, что в Советском Союзе существует свобода вероисповедания. В ФРГ почтовая бумага выходила с оттиском строящегося в Кисловодске храма. Тем не менее о конфликте между властью и верующими узнали за рубежом, об этом вещал «Голос Америки». Вскоре политическая ситуация в стране изменилась – Москву должен был посетить Президент США Рейган, что способствовало завершению строительства храма.
Крестовоздвиженскую церковь воздвигали в течение 11 месяцев. Храм был построен и освящён к 1000-летию принятия христианства на Руси. Строительство завершилось в 1988 году, а торжественное освящение состоялось 4 октября 1988 года. Внутренняя роспись Крестовоздвиженской церкви была завершена в 1996 году. Росписью руководил московский художник Николай Иванович Бурейченко.
Освящение храма происходило при большом стечении молящихся. В богослужении, которое совершал архиепископ Ставропольский и Бакинский Антоний (Завгородний), приняли участие представитель Патриарха Антиохийского при Патриархе Московском архимандрит Нифон, представитель Патриарха Болгарского при Патриархе Московском архимандрит Гавриил, настоятель храма во имя святой равноапостольной Марии Магдалины в Веймаре протоиерей Алексий Парфёнов и духовенство епархии.
Первым настоятелем Крестовоздвиженского храма стал один из старейших священников Ставропольской и Бакинской митрополии митрофорный протоиерей Сергий Лиманов.
Храм Воздвижения Креста Господня – исторический и культурный памятник регионального значения.
В храме имеются три придела – основной Крестовый и два боковых – в честь святителя Николая Чудотворца и в честь великомученика и целителя Пантелеимона. В храме находится великая святыня – чудотворная икона Божией Матери «Скоропослушница», написанная Афонскими монахами.
В настоящее время на территории храма располагается крестильная церковь в честь святых равноапостольных царя Константина и царицы Елены.
