В 1989 году под временный храм была приобретена часть частного дома, примыкающего к предполагаемой строительной площадке. Первая литургия в этом помещении состоялась на Пасху того же года. С Рождества Христова, 7 января 1990 года, богослужения стали проводиться в здании бывшего винного магазина, приобретенного для этих целей.
10 декабря 1989 года, в престольный праздник в честь Новгородской иконы Божией Матери «Знамение», состоялся первый крестный ход и освящение закладного камня в основание будущего собора. Архитектор М.С. Соколов разработал эскиз-идею храма, на основе которого кемеровский архитектор Геннадий Максимович Некрашевич совместно с конструкторами Ф.Ф. Бобковым и И.С. Шапором создали проект собора.
Строительство крестильного храма велось с 4 мая по декабрь 1990 года. 10 декабря 1990 года епископ Красноярский и Енисейский Антоний освятил этот храм в честь великомученика Георгия Победоносца. В 1991 году продолжалось возведение основного здания собора, особое внимание уделялось фундаменту. Мощность фундамента позволила увеличить высоту храма до 67 метров, что сделало его вторым по высоте в России. Строительство велось небольшими бригадами каменщиков, и к завершению потребовалось около 3,5 миллионов кирпичей.
В 1992 году на Пасху впервые над городом раздался колокольный звон: на временной звоннице были размещены колокола, изготовленные на Урале. 4 октября того же года начала работу Воскресная школа прихода, расположенная в отремонтированном здании бывшего лесоторгового магазина.
26 мая 1996 года состоялось освящение Знаменского кафедрального собора Святейшим Патриархом Московским и всея Руси Алексием II. В церемонии приняли участие епископы и священнослужители из различных епархий. С этого момента собор стал главным храмом Кузбасса.
Архитектурный ансамбль собора включает несколько храмов. Нижний храм освящен 14 октября 1995 года в честь святого равноапостольного князя Владимира. Справа от главного престола верхнего храма расположен придел 12 апостолов, освященный 21 сентября 2008 года. На территории собора находится крестильный храм в честь великомученика Георгия Победоносца, освященный 10 декабря 1990 года. Также здесь расположен храм святой великомученицы Екатерины, находящийся в здании Кемеровского епархиального управления, освященный 18 апреля 2010 года.
На территории собора расположены здание Епархиального управления Кемеровской епархии, различные епархиальные отделы, Дом паломника, православный склад-магазин, музей, трапезная и другие здания. За алтарем крестильного Георгиевского храма находится место погребения первого архиерея Кемеровской епархии, управлявшего епархией с 1993 по 2006 год.
Собор является центром духовной жизни региона, здесь регулярно проводятся богослужения, таинства и обряды. При соборе активно действует Воскресная школа, проводятся занятия для взрослых и детей, организуются благотворительные мероприятия и социальные проекты.
