Начало XIX века в Ставрополе ознаменовалось страшной эпидемией чумы, свирепствовавшей здесь с 1810 по 1816 годы. В память избавления от смертельной опасности на Крепостной горе был установлен каменный крест. На этом месте предполагалось построить новый каменный храм во имя святителя Николая.

В 1839 году Святейший Синод дал разрешение на постройку этого храма. Но уже через два года горожане обратились с просьбой о построении на этом месте церкви в честь Казанской иконы Божией Матери с двумя приделами — во имя святых Николая Чудотворца и Александра Невского. 24 мая 1842 года ставропольскому обществу было объявлено, что проект утвержден Государем.

В 1843 году Кавказская область с Черноморией были выделены в отдельную епархию. 8 июля состоялась торжественная церемония закладки храма, который освятил епископ Кавказский и Черноморский Иеремия. В 1847 году постройка храма была завершена, указом Святейшего Синода ему был присвоен статус кафедрального, а 4 ноября (22 октября по старому стилю) состоялось его освящение.

В 1858 — 1873 годах рядом с Казанским собором строится четырехъярусная колокольня.

Кафедральный собор славился своим церковным хором, регентом которого был ставропольский композитор и дирижер В.Д. Беневский. Под сводами собора была также устроена усыпальница, где в 1872 году был погребен епископ Феофилакт, причисленный к лику местночтимых святых, а в 1903 году — потомственный почетный гражданин города, церковный староста собора А.Ф. Нестеров.

Несмотря на то, что Казанский собор и колокольня подлежали охране как архитектурная ценность старины, в 30-х годах XX века собор был разрушен. Из колокольни сначала сделали радиомачту, затем парашютную вышку. Одно время ее хотели перестроить, сделав памятник героям гражданской войны, но в мае 1943 года она была взорвана. Оправданием для этого послужило то, что колокольня являлась ориентиром для налета на Ставрополь немецкой авиации.

Через почти полвека, 31 января 1991 года, решением президиума Ставропольского горсовета народных депутатов территория Крепостной горы была объявлена заповедной. Здесь начались археологические работы. В результате раскопок удалось установить точное расположение Казанского собора на местности.

В 1992 году было принято решение о необходимости воссоздания Казанского кафедрального собора и соборной колокольни. Постановлением главы администрации города Михаила Кузьмина был отведен участок под храмовый комплекс, составлены паспорт участка и задание на проектирование собора.

12 — 14 августа 1994 года, в праздник Изнесения Животворящего Креста Господня, Ставрополь посетил приснопамятный Патриарх Московский и всея Руси Алексий II. На Крепостной горе им был освящен камень, где позже стал возрождаться Казанский собор и «Царь-звонница».

В начале 2004 года по благословению епископа Ставропольского Феофана (Ашуркова) были начаты подготовительные работы по воссозданию комплекса Казанского кафедрального собора. 27 сентября этого же года состоялась закладка воссоздаваемого храма, а 4 апреля 2010 года, на Пасху, в Казанском соборе прошла первая служба.

16 — 17 ноября 2011 года в кафедральном соборе в честь Казанской иконы Божией Матери пребывала великая святыня Православия — Пояс Пресвятой Богородицы. Еще до прибытия Пояса о своем желании поклониться святыне заявили более ста тысяч паломников. С 1 по 10 мая 2012 года в Казанском соборе пребывал ковчег с частицей мощей святителя Николая Чудотворца. Поклониться мощам святителя пришли десятки тысяч ставропольцев.

13 декабря 2012 года чин великого освящения Казанского собора и Божественную литургию в новоосвященном храме совершил Святейший Патриарх Московский и всея Руси Кирилл. По окончании Литургии Святейший Патриарх объявил о присвоении собору статуса кафедрального.