Храм в честь Покрова Пресвятой Богородицы — старейшее из всех дошедших до наших дней каменное сооружение города Красноярска — был заложен в 1785 г. на пересечении главной магистрали города, Воскресенской улицы, с будущим Покровским переулком, проходящим по линии бывшей городской стены. В XVIII в. на Стрелке, в черте старого острога, стояла деревянная Покровская церковь, при большом пожаре 1773 г. сгоревшая. Храм Покрова приобрел и важное градообразующее значение.
Разрешение на строительство храма было получено прихожанами во главе с церковным старостой Даниилом Черкасовым и священником Михаилом Терским. Строительство велось под руководством специально для этой цели избранного человека — отставного дворянина Михаила Юшкова. Строителями были мастера из Енисейска: Степан Лещев, Василий Гатилов, Иван Помаскин, Алексей Казаретин, братья Иван и Савва Федоровы. Расходы по возведению церкви и, впоследствии, содержание причта взяли на себя прихожане. Пожертвования на строящуюся церковь были собраны как в г. Красноярске, так и в селах и деревнях Красноярского уезда.
Храм был построен в традициях сибирской ветви русского барокко, с применением фигурного и тесаного кирпича, с богатым декором и лепниной, в один этаж, с пятиглавым четвериком и многоярусной колокольней. Длилась основная очередь строительства 10 лет. 30 июня / 12 июля 1795 г. был освящен главный престол храма во имя Покрова Пресвятой Богородицы; южный, во имя свв. апп. Петра и Павла, на пять лет раньше — 8 / 21 января 1790 г.; северный во имя свт. Николая Чудотворца — 30 сентября 1790 г.
В храме имелось несколько особо чтимых реликвий, в том числе серебряный напрестольный крест с частицами свв. мощей многих угодников Божиих. В приходе имелись храмовая библиотека, насчитывавшая более 700 томов, одноклассная церковно-приходская школа, 4 министерских одноклассных училища, школа мещанского общества. Во время большого пожара в 1881 г. огонь уничтожил фресковую живопись на наружных стенах высокого четверика самого храма.
В 30-е годы XX в. с началом сталинских репрессий собор постигла судьба большинства российских храмов — он был закрыт и позднее передан воинской части. После начала изменения отношений власти и Церкви 8 мая 1945 г. был подписан договор о передаче церкви верующим, фактически действовать она начала с октября 1944 г. В 1945 г. будущий настоятель храма священник Николай Попов добился разрешения уполномоченного Совета по делам Русской Православной Церкви при СНК приобрести для Покровской и Николаевской церквей г. Красноярска «колокола и наружный колокольный звон».
Внутреннее убранство Покровского собора в 50-х годах XX в. претерпело изменения — во время ремонта более века украшавшие храм росписи были закрыты штукатуркой, а стены украшены лепным орнаментом, барельефными изображениями херувимов на фасадах, в полуглавиях храмового четверика.
В 1962 г. в разгар хрущевских гонений на Церковь собор был снова закрыт, в здании его разместились скульптурная мастерская, затем в августе 1978 г. — городской выставочный зал. Тогда же был разработан проект реставрации здания как памятника культуры, территорию частично привели в порядок, а темно-охристый фасад был перекрашен в кирпично-красный, с зеленой кровлей и куполами.
С началом перестройки 22 марта 1989 г. подписан долгожданный акт о передаче Церкви Покровского храма г. Красноярска — третьего на тот момент православного храма в городе. Освящение собора 19 июня того же года совершил митрополит Новосибирский и Барнаульский Гедеон (Докукин). Летом 1990 г. во вновь открытом Покровском соборе была совершена первая Божественная литургия архиерейским чином. После воссоздания Красноярской епархии храму был присвоен статус кафедрального собора.
4 декабря 1999 г. в ходе Первосвятительского визита Божественную литургию в Покровском соборе возглавил Святейший Патриарх Московский и всея Руси Алексий II.
Осенью 2006 г. начался капитальный ремонт, и храму был возвращен белый цвет, а купола и кровля обрели небесно-голубой (с лета 2012 г. — зеленый). Изменился и внутренний облик храма, ныне выполненный в белых и голубых тонах с использованием позолоты, с росписью стен фресками.
В марте 2008 г. в Покровском соборе под арочным сводом притвора напротив входа в центральную часть храма была найдена чудом уцелевшая фреска конца XVIII — начала XIX вв. с изображением иконы престольного праздника, которая позднее была реставрирована.
Приход храма — один из самых крупный в Красноярской епархии. За архиерейскими богослужениями, совершаемыми митрополитом Красноярским и Ачинским Пантелеимоном, часто присутствуют прихожане других приходов Красноярска и благочиннических округов епархии.
