Вопрос о строительстве нового храма встал после пожара 1810 года. Проект заводского архитектора С. Е. Дудина требовал больших затрат, поэтому был отвергнут властями. Вместо этого ему предложили обратить внимание на проект Андреевского собора в Кронштадте в качестве образца. Исходя из местных условий, Дудин откорректировал чертежи. Гранит был заменен на заводское литье, упрощены некоторые отдельные формы. После этого проект был принят, строительство завершилось в 1823 году. Центральный придел собора освящен в честь святого благоверного князя Александра Невского, северный – в честь Казанской иконы Божией Матери, южный придел – в честь святой великомученицы Екатерины, нижний, «пещерный», храм – в честь святых мучеников Власия и Модеста.

В 1929 году по требованию юношеской секции Союза воинствующих безбожников собор был закрыт. В том же году собор переоборудовали под клуб и разрушили колокольню. С 1930 года в здание собора размещался детский клуб и кинотеатр. Вернули собор прихожанам в 1990 году. В 1992 году после завершения проекта реставрации начались работы по возрождению собора. Закончили ремонт в 1993 году.

На территории собора построены иордань для освящения воды, новый крестильный храм, звонница. Освящение собора состоялось 2 января 1994 года.