Protestanten und Katholiken hatten sich nach der Reformation lange und nicht immer einvernehmlich die einzige Kirche Bochums, die heutige katholische Propsteikirche, geteilt. 1655 begann die lutherische Gemeinde mit Bau eines eigenen Gotteshauses. Weil der Gemeinde Geld fehlte, kamen Spenden aus Dänemark, Schweden, Kurland und Holland.

Die Pauluskirche ist nicht nach Osten und damit nach Jerusalem ausgerichtet, sondern folgt ganz pragmatisch dem Verlauf des damaligen Stadtgrabens. Das war möglich, weil der Gottesdienst im lutherischen Verständnis nicht mehr an eine solche Ausrichtung gebunden war.

1902 bis 1903 wurde die Kirche mit großen neugotischen Fenstern ausgestattet. 1943 brannte sie nach einem Bombenangriff bis auf die Außenmauern nieder. Beim Wiederaufbau erhielt das Gebäude sein heutiges, einer mittelalterlichen Dorfkirche entsprechendes Aussehen. Die modernen Fenster im Altarraum, um 1960 geschaffen vom Bochumer Künstler K. Willy Heyer, zeigen die drei Stationen der Wandlung des Saulus zum Paulus, dem Namenspatron der Kirche.

Um die Pauluskirche im Stadtbild besser zur Wirkung zu bringen, wurde ihr Turm 1949 erhöht, ein kleiner Platz geschaffen und die unmittelbare Nachbarbebauung niedrig gehalten. 1974 wurde der Innenraum erneut nach Plänen von Kurt Peter Kremer umgestaltet.

Neben der Kirche erinnert die »Trauernde Alte« des bedeutenden Kölner Bildhauers Gerhard Marcks an die Schrecken des schwersten ­Bombenangriffes auf Bochum am 4. November 1944. Sie wurde 1955 enthüllt und ist aus Basaltlava gehauen. Dargestellt ist ein alte Frau, die – wohl vergeblich – nach jemandem ausschaut.