Первая деревянная церковь во имя святых апостолов Петра и Павла в Сестрорецке была сооружена в 1722-1725 годах. Храм сгорел в 1730 году. В 1781 году на его месте возвели каменную церковь, для строительства которой использовали материалы от разрушившегося дворца Петра I в Дубковой роще. Этот храм также был уничтожен пожаром в 1868 году.
24 июля 1871 года на правом берегу реки Сестры заложили новый каменный собор по проекту епархиального архитектора Г.И. Карпова. Строительство велось подрядчиком Козловым. Храм выполнили в византийском стиле с приделом в честь иконы Божией Матери «Всех скорбящих Радость». Освящение состоялось 21 июня 1874 года митрополитом Исидором. В храм перенесли иконостас, утварь и образ Николая Чудотворца из домовой церкви Дубковского дворца.
В 1924 году церковь получила статус собора. В 1931 году храм закрыли, а в 1932-1933 годах разобрали. На его месте построили школу.
12 июля 2002 года состоялось освящение места для нового храма. Строительство по проекту архитектора Е.Ф. Шаповаловой велось с перерывами и завершилось в 2009 году. 11 октября 2009 года Патриарх Московский и всея Руси Кирилл совершил чин великого освящения. Храм возведен в память о российских моряках-подводниках, что связано с испытаниями «потаенного судна» Ефима Никонова на озере Сестрорецкий Разлив в 1721 году.
На территории храма находится часовня святителя Николая Чудотворца, заложенная в 2000 году. В фундамент часовни помещены капсулы с землей с мест базирования подводных лодок. Установлена Стена Памяти с мемориальными досками погибших субмарин. В храме ведется Книга Памяти с именами погибших подводников.