Строительство заводской церкви Александровского пушечно-литейного завода начато в июле 1826 года, по проекту архитектора Департамента горных и соляных дел Александра Ивановича Постникова. Также в строительстве принимал участие инженер Пьетро Карло Мадерни.
Работы по устройству иконостаса были выполнены под руководством мастера А. Боброва. Иконы написал художник А. С. Чижов.
27 января 1832 года Епископ Олонецкий и Петрозаводский Игнатием освятил главный престол храма.
Первым священником Александра-Невской заводской церкви стал Иаков Васильевич Васильковский.
В 1929 году храм был закрыт по решению общего собрания рабочих Онежского завода и Петрозаводского городского Совета. Здание передали краеведческому музею, при этом были снесены все 5 куполов, а внутри устроено межэтажное перекрытие, устроен подвал для хранения музейных экспонатов. Первая экспозиция музея в здании бывшей церкви открылась в 1931 году.
В 1991 году храм возвращён Петрозаводской епархии. Осенью 1993 года началась реставрация храма. Автор проекта реставрации — архитектор В. Г. Копнин. Внешний вид собора был восстановлен в точном соответствии с первоначальным (за единственным исключением — купола собора прежде никогда не золотились).
В 2000 году храм был освящен Патриархом Московским и всея Руси Алексием II.