В изданном в 1875 году четвертом выпуске «Историко-Статистических сведений о С.Петербургской епархии» датой постройки церкви св. апостолов Петра и Павла назван 1785 год. Позднейшие исследователи эту дату повторяют. Однако архивное дело из ЦГИА СПб «О постройке в Сердоболе новой церкви Петра и Павла в связи с неудобным расположением церкви Николая чудотворца» датируется 1794 год, а дело «Об освящении вновь построенной деревянной Петропавловской церкви в Сердоболе» 1799 год. Отсутствует городская православная церковь и на карте Сердоболя 1788-1790 годов.
Прошение о постройке новой церкви было отослано в 1794 году 16 октября того же года владыка гавриил митрополит Санкт-Петербургский выдал грамоту , разрешающую строительство деревянной церкви св. апп. Петра и Павла. Строительство продвигалось медленно, и только 30 июля 1799 года церковь была освящена. К 1825 году церковь обветшала. Началась переписка о финансировании ремонта. По Указу императора Николая I 30 мая 1830 года оплатить ремонт должна была Комиссия духовных училищ, что и было сделано. В 1839 году церковь все же отремонтировали.
В ИСС приводится описание церкви: по внешности она представляет вид креста; потолок ее ровный. Без купола; снаружи нет карнизов и каких-либо украшений Дощатая кровля устроена в два ската. На кровле две главы, крытые железом; кресты на главах деревянные, осьмиконечные, обитые белою жестью. Окна в здании продолговатые с железными решетками. Внутренние стены храма выкрашены светло-синею краской; пол из сосновых досок. Выкрашен желтой краской. Иконостас в три яруса. В нижнем ярусе поставлены иконы Спастеля, Божией Матери, Николая Чудотворца, Сергия и Германа, Александра Свирского и Арсения Коневского; во втором ярусе – лики апостолов, в 3–м пророки, на вершине – распятие; амвон возвышается на две ступени. Колокольня осьмигранная, над притвором. Описанный здесь храм заменил собою древнюю Никольскую церковь, которая находилась на острове в 2-х верстах от города. Построенный давно храм исправлен в 1839 году.
К середине XIX века здание церкви вновь обветшало, а к 1863 году стало рарушаться: фундамент развалился, протекала крыша, а колокольня с четырьмя колоколами грозила падением. Старая деревянная церковь свв. Апп. Петра и Павла, согласно указу СПб духовной консистории от 21 октября 1877 года была разобрана, сруб пошел на строительство дома для настоятеля церкви. Иконостас был демонтирован и находился в запасе до 1891 года, когда был установлен в перестроенной церкви св. Николая на острове Риеккалансаари. В 1877-1892 годах на месте разобранной церкви был пустырь, что показано на планах города.
Летом 1857 года Сердоболь посетил генерал-губернатор Великого княжества финляндского Ф.Ф. Берг. По окончании поездки он обратился в Святейший Синод об изыскании средств для построения в городе нового теплого храма. В октябре 1861 года разработка проекта и составления сметы строительства церкви в Сердоболе были поручены санкт-петербургскому епархиальному архитектору Г. И. Карпову.
В августе 1866 года проектирование и составление смет были окончены. Все документы на отвод земли оформлены. Для дальнейшего рассмотрения дело было представлено в Министерство Путей сообщения, в Департамент водяных сообщений, который «нашел проект на постройку каменной церкви по неблаговидности фасада неодобрительным, вследствие чего счел нужным заменить оный новым, с приданием фасаду более благовидного вида». Новый улучшенный проект был составлен архитектором-художником К. Е. Лазаревым. Служившим в Департаменте проектов и смет. От проекта Карпова новый проект отличался лишь мелкими деталями в оформлении фасада, более – ничем. 9 ноября 1866 года проект был предоставлен на утверждение Императора, 10 ноября утвержден. Т.к. средств на постройку практически не было, митрополит Санкт-Петербургский, Новгородский и Финляндский Исидор убедил и благословил коммерции советников братьев Георгия и Степана Петровичей Елисеевых построить в Сердоболе новый теплый пятиглавый деревянный храм на каменном фундаменте с колокольней, о чем свидетельствует письмо Г. Елисеева митрополиту Исидору от 8 января 1869 года разобравшись в состоянии дел и выслушав священника и церковного старосту, Елисеевы решили строить каменную церковь. Наблюдение за строительством церкви Елисеевы поручили академику архитектуры Н. П. Гребёнке. 22 августа 1869 года чертежи на постройку церки были отосланы в техническо-строительный комитет Министерства внутренних дел, глава которого приказал переделать проект, «придав церкви стиль более православный», что и было сделано архитектором Гребёнкой. 22 октября 1869 года министр внутренних дел утвердил проект.
Место, избранное под храм было освящено весной 1870 года. Этому предшествовали проблемы, вынуждавшие сменить участок для строительства церкви. К началу сентября 1871 года церковь была вчерне готова. 15 октября 1872 года священником церкви Федором Львовым в сослужении местных священников был освящен южный придел во имя успения св. праведной Анны. К 14 декабря 1872 года все основные работы по сооружению храма были окончены. Незавершенными из-за наступившей непогоды остались только малярные работы. Летом 1873 года церковь как снаружи, так и внутри была окрашена, и начались работы по подготовке остальных двух алтарей к освящению. 15 июля 1873 года утром был освящен малый северный придел во имя свв. Сергия и Германа Валаамских. Чин совершил Коневский архимандрит Израиль с иеромонахами из той же обители. Днем был освящен главный алтарь во имя св. апп. Петра и Павла. Таинство совершил специально прибывший на торжества митрополит Исидор в сослужении викарного епископа Выбогского Палладия. По представлению митрополита исидора за строительство церкви в Сердоболе братья елисеевы стали кавалерами орденов: старший, Григорий Петрович. Ордена св. Владимира 4-й степени, а младший, Степан, — св. Анны 2-й степени.
Основной объем церкви имеет в плане форму креста со скошенными углами и перекрыт куполом, поставленным на восьмигранном световом барабане. С востока к нему примыкает трехгранная алтарная апсида, а с запада четырехгранная шатровая колокольня. Основной объем имеет небольшие размеры по ширине, выделен аттиком фигурной формы. Рядом с куполом, мощныи и зрительно очень тяжелым, несколько теряются еще четыре главки, поставленные на глухих восьмигранных шеях. В декоративном решении церкви использованы элементы разных стилей, что относит архитектуру церкви к эклектике второй половины XIX века. резные золоченые иконостасы всех трех приделов были сделаны по рисункам архитектора Н.П. Гребёнки и изготовлены позолотных дел мастером К. Серебряковым. Главный иконостас был двухъярусным, иконостасы приделов – одноярусными. Первоначально на колокольне находилось 7 колоколов. Церковь обогревалась пятью изразцовыми печами, в настоящее время – четырьмя. Елисеевы не оставили церковь своим вниманием, неоднократно оказывая денежную и иную помощь.
В начале ХХ века в церковь было проведено электричество, а вокруг церкви высажена зеленая изгородь. В 1913 году в Сердоболе была учреждена епископская кафедра, а в 1925 году церковь св. апп. Петра и Павла получила статус кафедрального собора, поскольку в ней совершал богослужения глава Финской православной церкви архиепископ Герман. С началом Советско-финской войны и бомбардировок собор не пострадал. Колокола с колокольни были сняты и эвакуированы в Финляндию, самый большой колокол весом 1000 кг исчез со склада в Юваскюле. После перехода Сортавалы в состав СССР весной 1940 года собор был закрыт и осквернен. Клир вернулся в Сортавалу в феврале 1942 года. В здании собора начался ремонт, испорченный паркетный пол решили заменить на бетонный. Собор был освящен архиепископом Германом 1 августа 1943 года.
После Великой Отечественной войны главный престол был освящен во имя святителя Николая чудотворца. В 1946 году Сартавальская православня община прошла регистрацию и в декабре Совет Министров Карело-Финской ССР дал разрешение на открытие храма.. Один колокол для церкви был передан из Олонецкой церкви. В 1963 году в Сортавале был запрещен колокольный звон. Вновь колокола зазвучали в 1986 году.
В настоящее время Никольская церковь – главный храм Сортавальского православного прихода и благочиния Северного Приладожья. В сентябре 2001 года Патриарх Алексий II посетил Сортавалу, совершил краткий молебен в Никольском храме и посадил саженец дуба в церковной ограде.
21 мая 2002 года после того как алтарь Никольского храма был обновлен, архиепископ Петрозаводский и Карельский Мануил совершил чин освящения престола. Проект полной реставрации храмового алтаря был разработан Григорием Ткачуком, преподавателем Санкт-Петербургского высшего художественно-промышленного училища им. В.И. Мухиной. 7 декабря 2011 года восстановлены фигуры херувимов, расположенные под главным куполом внутри церкви. Головы херувимов были утрачены во время Великой Отечественной войны или во время ремонта в 1960-х годов. Осталась только одна голова, по аналогии с которой местным сортавальским скульптором были воссозданы недостающие.
