Ende des 19. Jahrhunderts wurde durch den Bevölkerungsanstieg im Westteil der Stadt Paderborn die Einrichtung einer neuen Pfarrkirche erforderlich. Sie entstand auf dem Gelände des ehemaligen Friedhofs vor dem Westerntor, wo die Grundsteinlegung Mitte Mai 1896 erfolgte. Nach Plänen des Diözesanbaumeisters Arnold Güldenpfennig (1830-1908) und unter Leitung der Bauunternehmer Josef Lukas und Bernd Kruse wurde die Herz-Jesu-Kirche im neugotischen Stil als Ziegelbau vollendet und am 25. Oktober 1898 geweiht.
Das das neue Gotteshaus war zunächst Filialkirche der Marktkirche am Kamp. Für die in Paderborn stationierten Soldaten wurde sie Garnisonskirche. Da vor allem dank des Eisenbahn-Ausbesserungswerks am Bahnhof weiterhin neue Bürger in den Westen der Stadt zogen, wurde die Herz-Jesu-Kirche am 1. Juli 1911 zur eigenständigen Pfarrei erhoben. Nunmehr als Filialkirche der Pfarrei Herz Jesu entstand an der Neuhäuser Straße die 1936 geweihte St.-Georgs-Kirche. Sie wurde zur Garnisonskirche für die Soldaten der nahen Infanterie- und Husarenkaserne und 1939 selbstständige Pfarrei.
Auf der Rückseite der Herz-Jesu-Kirche entstand an der Ecke Riemekestraße/Kirchstraße (heute Florianstraße) die im Mai 1899 eröffnete Marktkircher Mädchenschule. Über einem hohen Kellergeschoss aus Anröchter Sandstein erhoben sich plastisch geformte Sandsteinfassaden im Stil der italienischen Renaissance. Bereits 1905/06 wurde die Schule durch einen Erweiterungsbau für fünf weitere Klassen ergänzt.
Sowohl die Herz-Jesu-Kirche als auch die Mädchenschule wurden 1945 stark beschädigt. Während man die Kirche 1948/49 renovierte, baute man die Ruine der Schule 1950 zu einem modernen Geschäftshaus um. Zur neuen Herz-Jesu-Schule wurde die 1915 am Konrad-Martin-Platz errichtete Theodorschule, die erst 1971 ihren ursprünglichen Namen zurückerhielt.
An der Südseite der Kirche standen bis 2012 fünf (von ursprünglich sechs) aus Teutoburger Sandstein geschaffene Bildstöcke mit gusseisernen Relieftafeln, die Bibel- und Gebetsszenen zeigen und seit 1697 die Bahnhofstraße bzw. den Prozessionsweg zwischen dem Westerntor und der dem hl. Laurentius geweihten, im Zweiten Weltkrieg zerstörten Roms-Kapelle säumten. Zwei der Stöcke wurden 2012 auf die Rückseite der Kirche versetzt, um am Nebeneingang den Bau einer Rollstuhlrampe zu ermöglichen. In diesem Jahr begann zudem eine (zweijährige) Sanierung der Außenfassade.
