Построить церковь на кладбище изначально намеревалось ставропольское духовенство. Идея эта витала с 20-х годов XIX века. Но, наряду с материальными затруднениями, реализацию проекта тормозило эстетическое несоответствие величественной церкви облику окраинного кладбища.

Закладку первого камня произвели в 1847 году, а освятили храм на праздник Успения Божией Матери 15 августа 1849 года при многочисленном стечении народа.

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

Имя архитектора, увы, доподлинно неизвестно. Но очевидно, что его детище представляет собой образец русско-византийского стиля. Формы здания навевают ассоциации с Казанским Кафедральным Собором краевого центра и храмом Христа Спасителя в Москве.

Кое-что для внутреннего убранства храма было заимствовано из Троицкого собора. Многое было куплено и пожертвовано купечеством. Например, купец Ефим Дмитриев внес 1000 рублей серебром «на построение приличного иконостаса». В числе подарков церкви оказались редкие дорогие иконы.

Немного позже с южной стороны церкви был пристроен придел во имя Вознесения Господня. В 1998 году закипели работы по возведению придела с северной стороны.

Примечательно, что когда строители стали рыть котлован, они неожиданно наткнулись на уже готовый и фундамент из камня-ракушечника. Почему его законсервировали, также неизвестно. Но спустя столетие придел во имя Иверской иконы Божией Матери возвели на старом фундаменте.

Еще одна знаменательная деталь: освящение нового придела произвели 13 апреля 1999 года. Именно в этот день православные празднуют явление иконы Божией Матери на Афоне, а само явление этой иконы произошло в 999 году. Со дня явления Иверской иконы афонским монахам и до дня освящения возведённого в её честь придела прошло ровно 1000 лет. Чудеса, да и только!