Tahun 1897 paroki Surabaya (Kepanjen) menyerahkan wilayah Kediri, Blitar, Kertosono, Tulungagung kepada paroki St. Cornelius Madiun sebagai paroki baru. (Nganjuk-Brebek bagian dari Kediri, maka analoginya umat katolik Eropa di sini berada dalam penggembalaan Kediri). Pada tanggal 6 Juli 1880 ibukota kabupaten Brebek dipindah ke Nganjuk , sebidang tanah pemerintah seluas 1530 m2 di utara alun-alun di beli Tn. FE van der Meul seharga f 0, 15 untuk gereja orang Eropa pada tahun 1881.
Tahun 1925 berdiri paroki St. Vincentius a Paulo Kediri. Dua imam memiliki wilayah kabupaten Kediri-Nganjuk. Menurut Jaarboek tahun 1932, 1934, 1935 Rm. H. van Megen, CM dan H. Wessels, CM (2 imam dari Paroki Kediri) melakukan perjalanan pastoral bulanan ke Nganjuk, Kertosono dan Pare. Tahun 1935 berdiri sekolah rakyat Misie Yayasan Yohanes Gabriel di Babadan Pace dan Plangkat Bajulan. Tahun 1935 Rm. J. Wolters, CM menjadi kepala paroki Kediri dibantu Rm. H. Willems, CM dan Rm. JAM Klooster, CM.
Rm. Wolters, CM pada tanggal 4 Maret 1939 membeli tanah pekarangan yasan pensil no. 4 d I di Plangkat Bajulan milik Reksosoedarmo, F. Koesmin, Widjan dengan lebar tanah 0,035 Ha, 0,075 Ha, 0,05 Ha. (Tanah di Plangkat yang tersisa saat ini berupa bekas makam). Pada zaman Jepang tidak diketahui apakah ada kunjungan imam karena mereka ditawan Jepang. Diperkirakan peranan para rasul awam, khususnya para guru-guru yang berasal dari Jawa Tengah yang memelihara iman umat. Pada masa setelah kemerdekaan, misa dilakukan dari rumah ke rumah umat. Kapel di Utara alun-alun tetap dipergunakan.
Sejarah Gereja ini berdasarkan data dari Keuskupan Surabaya. Apabila muncul adanya tambahan informasi mengenai sejarah Gereja Katolik Paroki Santo Paulus Nganjuk bisa disampaikan ke Romo Kepala Paroki atau tim penulis kami di stpaulus34@gmail.com