Paroki Santo Cornelius Madiun merupakan Paroki tertua kedua di Keuskupan Surabaya setelah Paroki Kelahiran Santa Perawan Maria, Kepanjen, Surabaya. Berdirinya Paroki Santo Cornelius Madiun tidak lepas dari Sejarah Paroki Ambarawa. Paroki Santo Cornelius pada awalnya menjadi stasi bagian dari Paroki Ambarawa. Pada tanggal 2 Agustus 1859 dimana bagian tenggara stasi Semarang dipisah dan berdirilah Gereja Ambarawa yang menjangkau wilayah Ambarawa, Salatiga, Solo, Madiun, Pacitan. Pada tanggal 28 Juli 1897, Pastor Cornelis Stiphout, SJ yang sebelumnya menjabat sebagai Pastor Pembantu di Magelang di pindah ke Madiun, kemudian Madiun berubah menjadi Stasi dan terpisah dari Stasi Ambarawa. Wilayah Madiun pada waktu itu meliputi Karesidenan Madiun dan Karesidenan Kediri.

Pada tanggal 12 Maret 1899 Gereja Katolik di Madiun dibangun di sebelah barat Pastoran, yang sekarang dipakai sebagai Aula Bernardus. Perkembangan umat Katolik di Madiun semakin bertambah, maka bangunan gereja tersebut tidak mampu menampung umat yang ada. Oleh karena itu pada tahun 1937 dimulai pembangunan Gereja baru. Untuk menampung kegiatan peribadatan, sementara memakai Gedung Katholiek Sociale Bond. Gedung Katholiek Sociale Bond sendiri dibangun pada tahun 1934 yang berfungsi sebagai tempat pertemuan beberapa organisasi rohani seperti Wanita Katolik, Katolik Wandowo, Pengrukti Loyo, Kepanduan dan Palupi Darma. Gedung tersebut kini menjadi Balai Paroki.

Gereja tersebut diberkati pada tanggal 19 Juni 1938 oleh Mgr. Th. Backere, CM, Prefek Apostolik Surabaya, dengan nama pelindung Santo Cornelius, salah satu martir Gereja. Bangunan gereja tesebut yang dipakai sampai sekarang ini.

Perkembangan Gereja Katolik di Madiun tidak hanya sebatas pembangunan bangunan gereja saja, akan tetapi, lebih dari pada itu jumlah umat juga semakin berkembang. Perkembangan Gereja Katolik di Madiun telah melahirkan beberapa Wilayah seperti: