Der heutige Stadtteil Quakenbrück-Hengelage entstand jenseits der Stadtgrenze im Oldenburger Münsterland. Er gehörte politisch zum Gebiet der oldenburgischen Gemeinde Essen des Landkreises Cloppenburg, ragt aber in das Stadtgebiet Quakenbrücks, ja fast in die Altstadt, hinein. Kirchlich war offiziell die Pfarrkirche in Essen des Bistums Münster (Offizialatsbezirk Vechta) zuständig.

Weil die Katholiken dieses Gebiets seit jeher von der Quakenbrücker Gemeinde St. Marien betreut wurden und zuständige Pfarrkirche in Essen mehr als fünf Kilometer entfernt lag, wurde, um diesen „seelsorgerischen Missstand“ zu beseitigen, 1963/64 auf der Hengelage durch das Bistum Münster dort die St.-Paulus-Kirche als eigenständige Gemeinde errichtet. Den Neubau der Kirche schuf der Cloppenburger Architekt Rohling.

Nachdem der Essener Ortsteil Hengelage bereits mit der Gebietsreform 1972 politisch nach Quakenbrück eingemeindet wurde, wechselte die Zugehörigkeit der St.-Paulus-Gemeinde erst 2002 zum Bistum Osnabrück, obwohl die Gemeinde schon seit 1993 vom Pfarrer von St. Marien verwaltet wurde.

Das Patrozinium der Gemeinde ist am 29. Juni.