По преданию, в 1899 году Николай Александрович Базегский (03.02.1859 — 03.11.1918) пудожский купец 1-ой гильдии (единственный купец 1-ой гильдии среди всех местных купцов Олонецкой губернии) уточнил у мирского схода, что для любезного общества более важно на данном историческом этапе развития города: строительство моста через реку Водлу, для обеспечения устойчивого транспортного сообщения с Вологдой и Санкт-Петербургом, либо каменная церковь из красного кирпича? Общество подумало, и решило, что каменная церковь всё-таки лучше. И она была возведена в рекордно короткие сроки приглашенными из Петербурга специалистами. Чему в немалой степени способствовали ритмичные поставки строительного материала, завозившегося в Пудож круглогодично. И водным, и санным путем.
Уже 5 ноября 1903 г. церковь была освящена во имя святого Александра Невского. Храм был построен купцом Базегским в честь его отца – Александра Петровича (умер 08.11.1897 г.), похороненного на примыкающем к церкви фамильном кладбище.
Через три десятка лет, в печально известном 1937 г. был расстрелян последний настоятель храма отец Платон, а церковь переоборудована под хлебозавод, который проработал до средины 90-х годов прошлого века, при вхождении в рынок хлебозавод не выдержал капиталистической конкуренции и обанкротился. Конкурсный управляющий передал здание хлебозавода Администрации Пудожского муниципального образования. Администрация передала здание бывшего хлебозавода Муромскому (?) монастырю Русской Православной Церкви.
С 2003 г. монастырь потихоньку, в меру сил и финансовых возможностей, восстанавливает церковь.
При подготовке материала частично использована статья Константина Кучера "Пудож. Чем славен этот небольшой карельский город?", опубликованная 20.12.2010 г. в интернет-журнале ШколаЖизни.ру.