Ursprünglich gehörten Nieheim und Marienmünster einmal zur 1544 gegründeten Kirchengemeinde Bruchhausen, ab 1843 – zusammen mit Steinheim – zur neu gegründeten Kirchengemeinde Brakel. Erst mit der Gründung der Kirchengemeinde Marienmünster-Nieheim-Steinheim im Jahr 1864 vollzog sich die Auspfarrung dieses Bereiches auch der Brakeler Obhut.
Eigenständigen Gottesdienst gab es in Nieheim erst ab Februar 1853: Alle 6 Wochen hielt ein Geistlicher aus Peckelsheim im Gerichtssaal Gottesdienste ab. Doch als im November die sakrale Nutzung dieses Raumes untersagt wurde, wurde 1855 der Bau eine Betsaales mit einem Altar aus Tannenholz und Kanzel als Vorläufer der Nieheimer Kreuzkirche erörtert. 1856 wurde er im Haus 166 an der Marktstraße bezogen. Etwa zehn Jahre später jedoch entschloss sich die Gemeinde zu einem Kirchenbau, am 15. Mai 1868 wurde der Grundstein gelegt, am 29. September 1869 war die feierliche Einweihung dieses etwa 25 Meter langen neugotischen Gotteshauses mit eine einschiffigen Halle.
Doch die Freude an der neuen Kirche währte nicht lange: Am 17. Dezember 1869 riss ein gewaltiger Orkan die Spitze des Turms herab und zertrümmerte teilweise das Kirchendach. Erst 1876 konnte die Fertigstellung des neue Turmhelms gefeiert werden. Er war um ein Drittel kleiner als der alte. Mühsam war das Geld für die Bauarbeiten zusammengebettelt worden. Zu dieser Zeit war die weit ausgedehnte Diaspora-Gemeinde Marienmünster-Nieheim-Steinheim einer der ärmsten in der Provinz Westfalen. Sie hatte auf einer Ausdehnung von Langeland bis Löwendorf 280 meist unbemittelte Gemeindeglieder und einem Kirchensteueraufkommen von 260 Taler – allein die Turmreparatur kostete 400 Taler.
Erst im Vorfeld des 75-jährigen Jubiläums der Kirchengemeinde, 1939, wurden umfangreichere Renovierungsarbeiten durchgeführt. Malermeister Rieks versah den Altar und den Taufstein mit neuem schlicht-einfarbigen Anstrich mit Blattgoldverzierung. Die Orgel wurde – geschützt durch einen Vorhang – hinter dem Altar platziert.
Bis 1953 gab es nur einen alten Eisenofen, der den Kirchbau heizte. Mit Zuge einer weiteren Renovierung wurde eine Heissluftheizung eingebaut, die in einem Anbau Platz fand, in dem auch jetzt die Heizanlagen und die Sakristei untergebracht sind. Auch erhielten die Glocken einen elektrischen Antrieb. Weitere Umbauten erfolgten im folgenden Jahr: Zum Gedenken an die Opfer im 2. Weltkrieg wurde der untere Bereichs des Glockenturms zur Ehrenhalle umgebaut. Zur 100-Jahrfeier der Kirche in Nieheim, Michaelis 1969, erstrahlte dann vieles in und an dem Gebäude in neuem Glanz.
Nach Brand des Adventskranzes und der schweren Verrußung des Kirchenschiffes in der Nacht zum Jahreswechsel 2001/02 mußte der Innenraum der Kirche komplett restauriert werden.
Der Neueinzug nach Beseitigung der Brandschäden erfolgte am 4. Mai 2003.
Die neugotische Kirche hat durch den Anstrich der Bänke ein intensiveres Blau erhalten und neue, dem Stil entsprechende Leuchter.
