25 апреля 1825 года руководство Александровского пушечно-литейного завода получило разрешение Департамента горных и соляных дел на строительство заводской церкви; митрополит Новгородский Серафим благословил устроение нового храма. Для организации строительства была учреждена комиссия под председательством управляющего олонецкими горными заводами Адама Армстронга. В объявленном конкурсе проектов будущей церкви победил проект архитектора Департамента горных и соляных дел Александра Ивановича Постникова. Торжественная закладка нового заводского храма состоялась в июле 1826 года. Храм строился на выделенные казной средства и пожертвования мастеровых и служащих Александровского завода.
Строительство собора велось под руководством инженера Пьетро Карло Мадерни в 1826-1832 годах. Работы по устройству иконостаса были выполнены под руководством мастера А. Боброва из Кексгольма. Иконы написал художник А.С. Чижов. На колокольне церкви, в четырёхугольной башне на южной стороне, были установлены восемь колоколов различного веса. Епископ Олонецкий и Петрозаводский Игнатий 27 января 1832 года в день памяти святителя Иоанна Златоуста освятил главный престол храма во имя святого благоверного великого князя Александра Невского. Боковые приделы были освящены в честь и славу Пресвятой и Живоначальной Троицы и святого чудотворца Николая Мирликийского. В январе 1888 года при храме была открыта церковно-приходская школа на средства священника о. Василия Нименского и от пособия от Олонецкого епархиального совета для детей заводских служащих и мастеровых.
В 1929 году собор был закрыт по решению общего собрания рабочих Онежского завода и Петрозаводского городского Совета. Здание решено было передать городскому краеведческому музею, при этом были снесены все 5 куполов, а внутри возведено межэтажное перекрытие, устроен подвал для хранения музейных экспонатов. Первая экспозиция музея в здании бывшей церкви открылась в 1931 году. В 1991 году храм возвращён Петрозаводской епархии. Осенью 1993 года началась реставрация Александро Невского собора. Автор проекта реставрации — архитектор В.Г. Копнин. Внешний вид собора был восстановлен в точном соответствии с первоначальным, за единственным исключением — купола классицистического собора прежде никогда не золотились. Новое оформление интерьера, иконостас, киоты, паникадила и пр. не соответствует стилистике здания. 9 мая 1995 года епископ Петрозаводский и Карельский Мануил совершил первый торжественный молебен. В июле 1996 года на купола храма установлены золочёные кресты. 29 июня 1999 года были освящены и установлены на звонницу храма 8 колоколов, изготовленные в Воронеже по старинной технологии, весом от 7 кг до 1,5 тонны. Реконструированный собор украсил позолоченный иконостас, изготовленный на художественно-производственном предприятии РПЦ «Софрино».
3 июня 2000 года Святейший Патриарх Московский и всея Руси Алексий II освятил храм, который стал кафедральным собором Петрозаводской и Карельской епархии.
