Bis zum Beginn des 19. Jahrhunderts gehörte das Grundstück, auf dem die Kirche steht, der Familie Lopuchin, Verwandten der Zarin Jekaterina, der ersten Frau von Peter I. Das große Herrenhaus wurde im Brand von 1812 stark beschädigt. 1817 erwarb die Gemeinde der evangelisch-lutherischen Kirche der heiligen Apostel Peter und Paul das Grundstück, und das Haus wurde in einen Tempel umgebaut. Der Umbau wurde hauptsächlich mit Mitteln des preußischen Königs Friedrich Wilhelm III. finanziert. Die Kirche wurde 1819 geweiht. 1837 erhielt die Kirche die erste Orgel, auf der sechs Jahre später Franz Liszt auftrat und ein Konzert gab, das, so die Zeitzeugen, die Zuhörer stark berührte; einige Damen weinten, andere schnüffelten Ether.

In der Mitte des 19. Jahrhunderts, als die Zahl der Gemeindemitglieder 6000 überstieg, wurde beschlossen, eine neue Kirche zu bauen. Der neue Dom im gotischen Stil, entworfen von dem Architekten A. Meinhardt, wurde im Januar 1862 fertiggestellt. Zur Kostensenkung wurden Teile des alten Gebäudes verwendet. Ein Jahr später wurde auf den zweigeschossigen Glockenturm eine Glocke gehoben, die von Kaiser Wilhelm I. gespendet wurde.

Fünf Jahrzehnte später musste die Kirche erneut erweitert werden. 1903 fand ein Architekturwettbewerb statt, bei dem das Projekt des bekannten Architekten W. Walkot gewann. Das neue Gebäude in Form einer dreischiffigen Basilika mit einem Satteldach wurde jedoch von dem Akademiker der Architektur W. Kossow erbaut, der teilweise das Projekt von Walkot verwendete. Der Bau des neuen Gebäudes im neugotischen Stil begann um das alte herum, und erst nach Abschluss der Arbeiten wurde die frühere Kirche abgerissen.

Der Kirchenraum war für seine ausgezeichnete Akustik bekannt. 1913 erklangen hier zum ersten Mal die "Glocken" von Rachmaninow, und fünf Jahre später wurde das Requiem von Mozart mit der Teilnahme von A. Neschdanowa aufgeführt.

1918 erhielt die "Peter-Paul-Kirche" den Status einer Kathedrale Russlands und später der Sowjetunion. Doch bald wurde die Kirche geschlossen. Das Gebäude wurde in ein Kino namens "Arktika" umgebaut, und nach dem Krieg beherbergte es das Studio "Diafilm". Die Räumlichkeiten wurden umgestaltet, die Innenräume zerstört, die Orgel ging verloren. Vor dem Weltfestival der Jugend und Studenten im Jahr 1957 wurde der Turm der Kathedrale vollständig abgerissen.

In den 1990er Jahren wurde die Kirche den Gläubigen zurückgegeben, und Restaurierungsarbeiten wurden durchgeführt. 2010 wurde der Turm wiederhergestellt. Heute befindet sich in der Kirche eine Orgel aus dem 19. Jahrhundert, die zuvor der 1928 zerstörten lutherischen Kirche St. Michael in der Wosnesenskaja (heute Radio) Straße gehörte. Hier finden regelmäßig Konzerte mit Orgelmusik statt.

Zur Kirche gehört auch eine Kapelle, die in den 1890er Jahren im südlichen Teil des Kirchhofs nach einem Entwurf von F. Schechtel erbaut wurde.