Uns ist überliefert, dass es im 16. Jahrhundert in der Stadt eine Marienkirche (die schon genannte Wallfahrtskirche in Neukammer), eine Jacobikirche, vor dem Dammtor eine Nikolaikirche sowie eine Fronleichnamskapelle gab.

Mit der Reformation (1539) nahm die Zahl der Katholiken beträchtlich ab. Erst während der Regierungszeit von Friedrich dem Großen (1712/1740-1786) bildete sich eine feste katholische Gemeinde heraus, die sich ab 1746 in einem Raum im Lazarett zum sonntäglichen Gottesdienst versammelte. Die meisten Katholiken waren Angehörige des in Nauen stationierten Militärs. Sie wurden von auswärtigen Pfarrern geistlich betreut.

Als diese Garnison abgezogen wurde, blieb eine kleine Zivilgemeinde zurück.

Im Jahre 1810 kam der Toreinnehmer Johannes Reiß nach Nauen. Mit außergewöhnlichem Einsatz sammelte er eine Gemeinde um sich, ließ einen achtköpfigen Kirchenvorstand bestimmen und eine Kirchenordnung ausarbeiten. Die erste katholische Gemeinde hatte 50 Mitglieder.

Als die Gemeinde 1821 eine Tochtergemeinde der St. Hedwigs-Gemeinde in Berlin wurde, kamen häufiger Pfarrer nach Nauen. Sonst wurde der Gottesdienst vom Kirchenvorstand gehalten. Der Gottesdienstraum im Lazarett wurde 1843 gekündigt. Man beschloss, eine eigene Kapelle zu errichten. Zwischenzeitlich fanden die Gottesdienste im St. –Georgen-Hospital und in der evangelischen Kirche statt. In dieser Zeit schlossen sich die Kremmener Katholiken der Nauener Gemeinde an.

Der Kaufmann Hugo Busse schenkte seiner Gemeinde ein Grundstück, auf dem 1847 der Grundstein für eine kleine Kirche gelegt wurde. Sie wurde mit einem Kostenaufwand von 4000 Talern erbaut und am 1. Juni 1848 eingeweiht. Das Äußere dieser Kirche war schlicht. Vier Wandnischen im Inneren beherbergten Figuren der Maria, des Johannes und der Patrone Petrus und Paulus. Ein Schüler des bekannten Bildhauers Rauch namens Ackermann fertigte das Christuskreuz an.

An der Ecke Dammstraße/Gartenstraße entstand in den 90er Jahren des 19. Jahrhunderts das Schulhaus der katholischen Privatschule, das heute als Bibliothek dient.

Der Fürstbischof Heinrich von Breslau erhob Nauen 1862 zu einer "Missionspfarrei" für das Ost- und Westhavelland. Abwechselnd fanden die Gottesdienste in Nauen, Friesack, und Neustadt/Dosse statt. Im Mai 1894 wurde aus der "Missionspfarrei" eine vollberechtigte Pfarrei, die alle Ortschaften im Umkreis von 6 km erfasste.

Bis zur Jahrhundertwende wuchs die Zahl der Gemeindemitglieder auf fast 2.800 an: Die Kapelle wurde zu eng. Der Bau einer neuen Kirche wurde unumgänglich. Nach Plänen des Berliner Baumeisters Josef Welz erbaut, wurde die neoromanische Basilika 1906 feierlich eingeweiht. Ihr Bau hatte 80.000 Mark gekostet.

An der Errichtung waren 18 Handwerksbetriebe beteiligt, die vorwiegend in Nauen ansässig waren.

Im Glockenstuhl wurden 3 Glocken mit den Durchmessern 99 cm, 84 cm und 74 cm aufgehängt, deren Gewicht insgesamt 23 Zentner beträgt. In den Tönen gis - h - cis rufen sie die Gemeinde auch heute noch zum Gottesdienst.