27 января 1832 года в городе Петрозаводске при Александровском заводе был освящён главный престол церкви во имя святого Александра Невского.

Строительство храма связано с именем императора Александра I, который посетил город Петрозаводск в 1819 году. Ему был представлен на рассмотрение проект заводской церкви, на строительство который он затем выделил денежный взнос. Кафедральный собор было решено возвести в честь победы в Отечественной войне 1812 года.

Торжественная закладка храма состоялась 22 июля 1826 года. В его основание были помещёны свинцовый ящик с памятными серебряными и бронзовыми медалями с изображениями императоров Александра I и Николая I, а также медная позолоченная доска с памятной надписью. Строительство церкви велось по проекту известного петербургского архитектора Александра Посникова в стиле высокого классицизма. «Постройка произведена из лучших материалов на прочном фундаменте с гранитным тесаным цоколем и тесаными же из зеленоватого камня тремя крыльцами и площадками <…> во всем согласно плана, фасада и профиля, составленных архитектором Постниковым…».

На строительстве храма работали ярославские каменщики и крестьяне Олонецкой губернии под руководством швейцарского подданного Пьетро Карло Мадерни. Отделочные работы здания выполняли мастера из Санкт-Петербурга и Костромской губернии.

В одной из башен собора располагалась колокольня. Большую часть икон внутри здания, представляющих собой копии известных икон из церквей Москвы и Санкт-Петербурга, выполнил художник из Санкт-Петербурга Александр Чижов. В то время храм представлял собой одно из самых больших и красивых каменных зданий в Петрозаводске.

Часть средств на возведение собора пожертвовали работники Александровского завода и жители города.

При церкви находились четыре часовни, а также церковно-приходская школа для детей заводских служащих и мастеровых.

В 1929 году церковь была закрыта, здание передано Краеведческому музею, который размещался здесь в течение 64 лет. В здании был переделан центральный купол, разобраны звонницы, сделаны этажные перекрытия. Но в целом музей сохранил здание.

15 июня 1990 года Совет Министров Карельской АССР принял решение о возвращении храма Петрозаводской и Карельской епархии. В 1994 году начались работы по реконструкции Александро-Невского кафедрального собора. Реставрация храма продолжалась 7 лет.

Зданию был возвращён первозданный архитектурный облик. На церковные купола были установлены святые кресты, на звонницы храма – колокола, вылитые по старинной технологии на воронежском заводе «Вера». Самый большой из колоколов весит 1150 кг. Его назвали «Александровским». На нём отлиты имена меценатов, благодаря которым были изготовлены и доставлены колокола. Собор украшен позолоченным иконостасом, выполненным на художественно-производственном предприятии Русской Православной Церкви «Софрино». Каркас иконостаса изготовлен работниками Онежского тракторного завода и судостроительного завода «Авангард».

3 июня 2000 года кафедральный собор во имя святого благоверного великого князя Александра Невского Петрозаводской и Олонецкой епархии вновь был освящён Патриархом Московским и Всея Руси Алексием II.

3 июня 2010 года рядом с собором состоялось торжественное открытие памятника А. Невскому, авторами которого являются скульптор, профессор Санкт-Петербургской Художественно-промышленной Академии Валентин Григорьевич Козенюк, архитектор А. Гречкин. Памятник и собор представляют собой единый ансамбль.

Святой князь Александр Невский с давних времен считался небесным покровителем Новгородских земель, в состав которых входили и карельские погосты. Предание гласит, что если в городе есть действующий храм в честь его имени, в этот город никогда не войдёт враг.