Pfarrerin Steffie Langenau und Superintendent i.R. Dieter Lorenz berichteten, dass die Kirchengemeinde im Jahr 1880 für die aus dem „erweckten“ Ravensberger Land zugewanderten Arbeitskräfte gegründet wurde, und zwar zunächst als „Filialgemeinde“ (Tochtergemeinde) der lutherischen Gemeinde Bergkirchen. Weil der Weg von Bergkirchen nach Bad Salzuflen zum Gottesdienst für den Pfarrer auf Dauer zu beschwerlich war, wurde in den Jahren 1891/92 hoch über der Stadt die ev.-luth. Kirche gebaut.
Anfangs entsprach die im Grundriss kreuzförmige Kirche gänzlich dem Modelltypus eines evangelischen Gotteshauses des 19. Jahrhunderts. Die Kirche entstand nach einem Entwurf des Architekten Hermann Held (Bielefeld-Bethel) unter der Bauleitung von Karl Siebold (ebenfalls Bielefeld-Bethel). Karl Siebold (1854 - 1937) war Kirchenarchitekt und als Leiter der Bauabteilung der von Bodelschwingh‘schen Stiftungen in Bethel Hermann Helds Nachfolger. Siebold baute in Lippe auch die ev.-ref. Kirche Helpup (1906/07).
In den Jahren 1908/09 wurde die Bad Salzufler Kirche durch Karl Siebold um den Westteil mit dem 25 Meter hohen Turm erweitert. 1945 und 1946 mussten die Lutheraner in Bad Salzuflen auf ihre Kirche verzichten, weil die britischen Streitkräfte sie als Garnisonkirche nutzten.
Im Rahmen einer umfassenden Renovierung 1969 erhielt die „Erlöserkirche“, wie sie seit dem Bau der lutherischen „Auferstehungskirche“ (1966) hieß, einen neuen, schlichten Sandsteinaltar und einen neuen Taufstein, den die katholische Kirchengemeinde stiftete. Dieter Lorenz: „Dieses Geschenk war als gutes Zeichen der Ökumene gemeint, weil die Taufe alle christlichen Kirchen miteinander verbindet.“
Bei der Renovierung 1969 wurden die Wände hell gestrichen. Die originale Holzkanzel von 1892 behielt ihren Platz neben dem Altar. Allerdings wurde die Orgel von der Empore ins „Erdgeschoss“ verlegt, und zwar ins südliche Querschiff.
Die Hamburger Firma Rudolf von Beckerath baute 1971 die neue Orgel für die Erlöserkirche. Auf dem Instrument gestaltete der Kirchenmusiker und Hochschullehrer Prof. Dr. Bernd Scherers den musikalischen Teil des Orgelsommer-Nachmittags und stellte dabei die Klangfülle der Orgel eindrucksvoll vor. Das mit Virtuosität und Einfühlungsvermögen vorgetragene musikalische Programm verdiente sich zusätzlich die Bezeichnung „international“.
Gespielt wurden Stücke des Franzosen César Franck (1822 - 1890), des Engländers Alfred Hollins (1865 - 1942), des Polen Mieczysław Surzynski (1866 - 1924), des Belgiers Flor Peeters (1903 - 1986) und des Kanadiers Denis Bedard (geb. 1950).