Официально приход Русской Православной Церкви зарегистрирован в администрации города Норильска 21 июня 1991 года. И уже 7 июля этого же года Преосвященнейшим Антонием, Епископом Красноярским и Енисейским (ныне - Архиепископ) совершается освящение места и закладка храмов в честь образа Божией Матери «Всех скорбящих Радость» и крестильного - во имя Рождества Святого Пророка и Крестителя Господня Иоанна. Церковь была заложена на том самом месте, где еще каких-то сорок лет назад располагались бараки для политзаключенных и административные здания НорильЛАГа, одного из самых грозных форпостов Сталинской репрессивной машины.
Стараниями Горнометаллургического комбината и усилиями самоотверженного людского труда кирпичное здание малого крестильного храма было воздвигнуто в рекордные сроки. Уже в 1993 году в храме на Святую Пасху было совершено первое Богослужение, а через несколько месяцев Высокопреосвященнейший Владыко Антоний совершает Великое освящение новосооруженного храма и Алтаря. Вскоре, после освящения места начинается и строительство Собора во имя иконы Божией Матери «Всех скорбящих Радость».
В 1997 году в Соборе на престольный праздник проходит первое Богослужение. К 2003 году храм украшал город Норильск во всей своей красе. 27 июля 2003 года Великое освящение храма совершает Его Высокопреосвященство, Высокопреосвященнейший Архиепископ Антоний. По ходатайству Владыки Святейший Патриарх Московский и всея Руси Алексий II присваивает храму статус Собора.
В Соборе особо чтится образ Божией Матери «Всех скорбящих Радость», который расположен в правом киоте в центре храма. Также в алтаре храма хранится ковчежец с 13 частицами Святых мощей угодников Божиих, среди которых мощи святителя Николая Чудотворца, св. благоверного князя Александра Невского, святителя Феодосия Черниговского, прав. Феодора Ушакова и др.