Община прихода была образована в 1988 году, в год празднования тысячелетия Крещения Руси.Обращение верующих жителей города о регистрации православной общины состоялось 8 июня 1988 года.Положительное решение о её регистрации и отводе земельного участка под строительство церкви было принято после вмешательства Совета по делам религий при Совете Министров СССР.В 1989 году настоятель храма обратился к епископу Вятскому и Слободскому Хрисанфу с просьбой о благословении на совершение малого освящения и проведение богослужений в здании, реконструируемом из жилого деревянного барака.Благословение было получено, и 11 декабря 1989 года во Всехсвятской церкви была совершена первая Божественная литургия.
Закладка каменного храма состоялась 14 октября 1991 года на крутом берегу реки Вятки, вблизи места, где ранее находилась разрушенная в 1930-е годы сельская церковь Рождества Пресвятой Богородицы. Строительство велось поэтапно: 21 сентября 1994 года на строящемся храме был установлен первый (центральный) купол. В этот же день город с пастырским визитом посетил Патриарх Московский и всея Руси Алексий II, который поднялся на строящийся храм и выступил с амвона действующей деревянной церкви.
Храм представляет собой двухэтажное каменное здание с одиннадцатью куполами. Высота главного купола составляет 35 метров, он увенчан 4-метровым крестом весом 4 тонны. Высота звонницы достигает 47 метров (с крестом — 54 метра). Колокол-благовест весом 85 пудов был поднят на звонницу 3 декабря 2002 года; он был отлит на Кировском заводе обработки цветных металлов.
В нижнем храме находятся две иконы с частицами мощей: архиепископа Луки и преподобномученика Кукши Печерского, а также чудотворная Казанская икона Божией Матери, известная помощью тем, кто не мог родить детей. В иконостасе нижнего храма размещена единственная в епархии икона Собора вятских святых. В верхнем храме находится единственная в Русской Православной Церкви Вятская икона Пресвятой Богородицы.
Престольный праздник нижнего храма отмечается 21 сентября (Рождество Пресвятой Богородицы), а верхнего храма — во второе воскресенье после Пятидесятницы (Собор всех святых, в земле Русской просиявших).
Священники Всехсвятского храма окормляют домовую церковь в Кирово-Чепецком доме-интернате для престарелых и инвалидов, освящённую в честь иконы Божией Матери «Всех Скорбящих Радость».
