С православными духовными центрами Северного Кавказа была связана жизнь многих поколений наших предков. И здесь особое место занимал Ставрополь, где более полутора веков назад был учрежден центр Кавказской и Черноморской епархии.
Самая первая церковь в рождавшемся Ставрополе была возведена в стенах крепости. «Нет сомнения, - сообщалось в «Сборнике сведений о Северном Кавказе» № 6 за 1910 год, - что по личному указанию Суворова в 1780 году в Ставропольской крепости была выстроена первая «Церковь Божия» для полка Владимирского драгунского, в которой иконостас полковой поставлен...»
Церковь Владимирского драгунского полка с матерчатым иконостасом, которая была освящена в честь Святителя Николая, по сохранившимся планам крепости находилась в её центральной части.
В начале XIX столетия, в связи с постройкой ряда новых укреплений в более южных районах, Ставропольская крепость утратила свое прежнее значение.  Как военный объект, видимо, она существовала вплоть до 1812 г., когда Таганрогский драгунский полк, дислоцировавшийся в крепости, был отправлен в действующую армию, сражавшуюся с Наполеоном.

Деревянная церковь крепости после ухода гарнизона была сломана кавказскими содержателями (откупщиками) питейных сборов: комиссионером Задонским и купцом Шугаевым, и продана в г. Георгиевск, где по одной из версий, была установлена на кладбище (переименована в церковь Покрова Пресвятой Богородицы), по другой – перестроена в 1845  г. (Никольская церковь) и сохранилась до наших дней.

В 1821 г. Белгородский уланский полк (бывший Таганрогский драгунский), проходя через Ставрополь и обнаружив факт исчезновения своей церкви, возбудил по этому поводу соответствующее дело перед управлением Кавказской области.
В статье Г.Н. Прозрителева «Опись делам, имеющим военное значение...», помещенной в V-м выпуске «Трудов Ставропольской ученой архивной комиссии», указывается наличие прошения Задонского и Шугаева начальнику Кавказской области «о дозволении перевезти из Ставрополя в Георгиевск деревянную церковь, принадлежащую Таганрогскому драгунскому полку», а также наличие дела, возбужденного Белгородским уланским полком в связи с тем, что он «по выступлении из города передал церковь «под надзор» земскому начальству, которое без ведома полка продало её».
Переписка по данному вопросу, содержащая 44 листа, была начата 5 ноября 1821 г. и закончена в 1829 г. Факт слома церкви говорит о фактической ликвидации крепости, что также подтверждается тем, что на плане Ставрополя, датированном 1833 г., хранящемся в Ставропольском государственном музее-заповеднике, крепостные постройки не указываются, за исключением офицерской казармы, частично сохранившейся до наших дней.
В связи с переносом деревянной церкви, планировалось в честь Святителя Николая построить новый храм в юго-восточной части крепости, что, однако, не было исполнено. Лишь в 2004 г. на территории Крепостной горы около Казанского кафедрального собора в честь указанного святого была построена церковь.
После того как деревянная полковая церковь была разобрана, на её месте поставили каменный крест, который до наших дней не сохранился.

В 2000 г., в ознаменование наступления третьего тысячелетия, недалеко от этого места установили новый памятный крест. Открывал и освящал его митрополит Ставропольский и Владикавказский Гедеон. Автор памятника – ставропольский архитектор И. П. Ефремов.