Die ersten Lutheraner kamen gegen Ende der Regierungszeit (1524- 1533) des Fürsten Wassili Iwanovitsch nach Moskau. 1559 gründeten sie die erste Gemeinde und nannten sie nach dem Erzengel Michael. 1576 wurde im sogenannten „Deutschen Viertel" am rechten Ufer des Jausa- Flusses eine hölzerne Kirche gebaut, die erste lutherische Kirche nicht nur in Moskau sondern in ganz Russland. 1626 gründeten die lutherischen Armeeangehörigen, die einen wesentlichen Teil der Michaelisgemeinde ausmachten, eine eigene Gemeinde unter dem Namen der Apostel Peter und Paul. Ihr Kirchengebäude stand im Zentrum von Moskau, in der „Weißen Stadt". Später wurden alle Nicht-Orthodoxen in das neu errichtete Jausa-Viertel außerhalb der Stadt umgesiedelt. 1670 wurde dort eine Kirche errichtet auf einem Grundstück, das der Gemeinde von General N. Baumann geschenkt worden war. 1695 wurde in Anwesenheit des Zaren Peter I. ein neues, steinernes Kirchengebäude eingeweiht, für welches er ein Jahr zuvor den Grundstein gelegt hatte.

Nach den Feuersbrünsten 1737 und 1748 wurde die Kirche rekonstruiert. 1781 wurden das Pfarrhaus und die gemeindeeigene Schule gebaut. Von diesem Komplex blieb nach dem großen Brand Moskaus im Jahre 1812 nur die Schule erhalten, und einige Jahre lang wurden dort auch die Gottesdienste abgehalten.

1817 erhielt die Gemeinde die Erlaubnis, das Lopuchin-Anwesen in der Nähe der Pokrovka-Straße zu erwerben. Mit finanzieller Hilfe des preußischen Königs Friedrich Wilhelm III. und mit Unterstützung des Zaren Alexander I. wurde im Juni des folgenden Jahres damit begonnen, das erworbene Gebäude zu einer Kirche umzubauen, welche am 18. August 1819 eingeweiht wurde. Die Schule wurde 1824 wieder eröffnet und wurde später in ein Internat umgewandelt.

Mitte des 19. Jahrhunderts, als die Anzahl der Gemeindeglieder 6000 überstieg, wurde beschlossen, die Kirche nach den Plänen des Architekten A. Meinhardt umzubauen. Die Arbeiten wurden im Januar 1862 beendet. Ein Jahr später wurde eine Glocke auf dem Turm angebracht, ein Geschenk von Kaiser Wilhelm I. In der Kirche wurden nicht nur Gottesdienste gefeiert, sondern auch Konzerte veranstaltet. 1843 konnten die Moskauer sogar das Orgelspiel von Franz Liszt hören. Im Jahre 1892 erhielt die Kirche eine neue Orgel mit 42 Registern, gebaut von der Firma E. F. Walker. Anfang des 20. Jahrhunderts zählte die Peter und Paul-Gemeinde bereits ca. 17.000 Mitglieder. Deshalb wurde beschlossen, eine neue Kirche zu bauen. Die Bauarbeiten begannen 1903 nach den Plänen des Architekten W. A. Kossow, eines der Architekten der orthodoxen Christus- Erlöser-Kirche. Am 18. Dezember 1905 wurde die neu erbaute Kirche als Bischofskirche des Moskauer Konsistorialbezirkes eingeweiht. 1924 erhielt sie den Status der Bischofskirche der Evangelisch-Lutherischen Kirche in derUdSSR.

Im November 1936 wurden Pastor Alexander Streck und der Kirchengemeinderat verhaftet, und die Gottesdienste verboten. 1937 wurde die Kathedrale zum Kinotheater „Arktika" umfunktioniert, und später zum Studio "Diafilm". Dabei wurde das Innere der Kirche vollständig umgebaut. Vor Beginn der Weltjugendspiele 1957 wurde auch die Turmspitze demontiert.