Die Pauluskirche – oben auf dem Laagberg - bildet die gefühlte Spitze dreier sehr unterschiedlicher Wohnviertel: dem Laagberg, dem Hageberg und dem Wohngebiet am Stadtwald.
Sie entstand nach einem Entwurf des Architekten Gerhard Langmaack und wurde als fünfte evangelische Kirche am 8. Oktober 1960 vom Landessuperintendenten Peters aus Celle geweiht. Seiner Festrede lag der Korintherbrief, Kapitel 3 zugrunde: "Denn wir sind Gottes Mitarbeiter, ihr seid Gottes Ackerwerk und Gottes Gebäu."
Die Pauluskirche hat 450 Sitzplätze und wird von Osten durch den Kirchturm betreten. Der Besucher wendet sich dann nach links, durchschreitet einen Vorraum und betritt das Kirchenschiff mit Blick auf den um drei Stufen erhöhten Altar, und einen 7x5 m großen Wandteppich darüber, nach einem Entwurf von Johanna Schütz-Wolff. Der Wandteppich war ein Geschenk der Stadt an die Pauluskirchengemeinde und stellt den wiederkommenden Christus dar, der den Engeln den Auftrag gibt, die Ernte einzubringen. (Offenbarung des Johannes, Kapitel 14.)
Der Altarraum wird beleuchtet durch ein östliches Seitenfenster, vor dem das Taufbecken steht. Taufbecken, Altar und Kanzel bilden mit dem Chorraum eine Linie. Die Orgel der Firma Ott aus Göttingen wurde 1964 eingebaut und umfasst 24 Register.
