Церковь была построена на городском кладбище на средства одного их крупнейших предпринимателей-торговцев Олонецкой губернии конца ХIХ века и начала ХХ века пудожского купца 1-й гильдии Николая Александровича Базегского.
Закладка храма состоялась 7 мая 1902 года. Строительство велось из кирпича, производившегося на собственном небольшом кирпичном заводе Н.А. Базегского. В начале 1903 года строительные работы были завершены, церковь освящена. Постройка выполнена в русском стиле. Каменные храмы такого типа были характерны для провинциальных городов начала ХХ века. Церковь состоит из прямоугольной в плане храмовой части с притвором и более узкого трехстенного алтаря. Крыша храма в соответствии с церковными канонами венчалась пятью главами луковичной формы на высоких восьмигранных кирпичных барабанах.
В 1906 году при церкви также на средства Н.А. Базегского была построена и освящена каменная четырехъярусная колокольня. Три нижних яруса – квадратные в плане, верхний, открытый ярус звона – восьмигранный. Колокольня завершалась крупной луковичной главой. Фасады церкви и колокольни были оформлены в русском стиле. Сложившийся храмовый комплекс стал играть важную градостроительную роль в застройке исторической части города Пудожа. За постройку церкви Н.А. Базегский был награжден орденом Св. Анны 3-й степени, а колокольни – орденом Св. Анны 2-й степени.
В начале 1930-х годов церковь Александра Невского закрыли и передали под мастерские и склад Пудожской МТС, а в 1939 года – под Дом обороны «Общества содействия обороне, авиационному и химическому строительству». В период Великой Отечественной войны в ней размещалась хлебопекарня, затем склад «Заготзерна». В начале 1960-х годов здание было приспособлено под молокозавод. В связи с этим с церкви и колокольни были сняты купола, на колокольне разобран верхний ярус звона, заложено несколько окон, пристроены дополнительные помещения, почти полностью закрывающие нижние ярусы колокольни и фасады церкви. Интерьеры церкви были сильно искажены при размещении оборудования молокозавода. В результате храм перестал играть роль архитектурной доминанты.
В начале 2000-х годов храмовый комплекс был передан в собственность Руссой Православной церкви. С этого момента началось восстановление церкви и обустройство подворья Муромского монастыря. В связи с многочисленными перестройками потребовалось проведение большого объема работ по восстановлению храмового комплекса. На сегодняшний день силами прихода над храмовой частью установлена глава, заменены окна, двери, заканчивается внутреннее обустройство церкви, установлены хоры, иконостас, восстанавливается колокольня, подводятся инженерные коммуникации. В переходе, соединяющем церковь и колокольню, идет ремонт помещения, в котором разместится вечерняя школа. Несмотря на то, что работы еще не завершены, церковь уже действует, в ней проводятся службы. Храм Александра Невского вновь стал православным центром старинного города Пудожа.
