Awal mula berdirinya gereja Kristus Raja diawali dengan kedatangan 5 (lima) orang imam Lazaris sebagai misionaris pertama untuk misi Surabaya pada tahun 1923. Mereka adalah Pastor Dr. Th. de Backere, CM; Th. H. Heuvelmans, CM; Cornelius Klamer, CM; E. Sarneel, CM; dan G.J. Wolters. Di Surabaya Pastor Dr. Th. de Backere, CM bertugas sebagai Superior Missionis (semacam Vikaris Episkopalis*), Superior Religiosus dan Romo Kepala Paroki Kelahiran Santa Perawan Maria.
Pada tahun 1927 dibentuklah Stasi Ketabang, yang sekarang lebih dikenal Paroki Kristus Raja. Romo perintisnya ialah Romo G.W. Litjens, CM seorang Pastor Pemelihara Rohani untuk Angkatan Laut Kerajaan Belanda (Aalmoezenier) yang ditugaskan di Ketabang. Surabaya menjadi Prefektur Apostolik* pada tanggal 15 Februari 1928 dan Mgr. Dr. Th. de Backere, CM dikukuhkan menjadi Prefek Apostolik* pada tanggal 16 September 1928.
Sebagai pusat kegiatan di Stasi Ketabang maka dibangunlah gedung sekolah di Derxstraat (Jl. Residen Sudirman), yang peletakkan batu pertamanya jatuh pada tanggal 1 April 1929 oleh Mgr. Dr. Th. de Backere, CM. Sekolah tersebut diberkati pada bulan Juli 1929 dan diresmikan sebagai sekolah pada bulan Februari 1930 dan di beri nama “HIS (Hollands Indische School) Santa Theresia".
Pada saat itu Stasi Ketabang belum mempunyai gedung gereja. Oleh karena itu, kegiatan besar seperti Natal dan upacara Misa Kudus dilakukan di gedung sekolah Santa Theresia. Kadang-kadang kegiatan gereja juga dilakukan di HBS (Hoogere Burgerschool) di HBSstraat atau sekarang SMA Komplek di Jl. Wijaya Kusuma.
Stasi Ketabang yang terus berkembang membuat sekolah Santa Theresia dibanjiri murid baru. Selanjutnya dibangunlah sebuah sekolah lagi pada tahun 1933 yaitu sekolah Santa Yohanes Gabriel, yang terletak di pojok Derxstraat (Jl. Residen Sudirman) dan Mulolaan (Jl. Teratai). Lambat laun gedung pastoran dibangun di samping sekolah Santa Yohanes Gabriel dan selesai pada Februari 1933.
Sejak tahun 1938 sekolah Santa Theresia menjadi Santa Theresia Hulp Kerk atau Gereja bantu Santa Theresia atau gereja tetap Stasi Ketabang. Nama gereja, yang semula Santa Theresia Hulpkerk, diubah menjadi Kristus Koningkerk atau Gereja Kristus Raja.
Ketika tentara Jepang masuk pada Maret 1942 di Surabaya, mereka mengancam dengan akan melakukan pengeboman di atas Kota Surabaya. Sejak saat itu gereja bantu Kristus Raja menjadi sepi karena umatnya sebagian besar adalah warga Belanda. Sekolah Santa Theresia dan gereja Kristus Raja diduduki tentara Jepang dan digunakan sebagai pos penjagaan. Tidak hanya itu tempat kediaman Pastur (pastoran) di Ketabang hampir diambil alih oleh Jepang, tapi pada akhirnya Pastoran Ketabang terhindar dari penyitaan. Puncaknya pada bulan September 1943 semua pastor atau romo Stasi Ketabang yang berkebangsaan Belanda ditangkap dan diinternir oleh tentara Jepang. Mereka dibawa ke penjara Bubutan. Akibat dari ditangkapnya romo berkebangsaan Belanda, maka kegiatan rohani diasuh oleh dua romo dari Jawa, yaitu Romo PCL Dwidjosoesanto, Pr dan Romo JHC Padmosapoetro, Pr.
Setelah Jepang kalah perang, romo dan rohaniwan kembali dari interniran. Salah satunya adalah Romo Dr. J. Haest, CM. Sedangkan Romo E van Mensvoort kembali ke Ketabang. Di masa kemerdekaan, meski masih banyak keterbatasan, jumlah umat gereja dan Paroki Kristus Raja terus bertambah. Gereja bantu sudah tidak lagi menampung umat lagi.
Maka pada tahun 1956, Romo M. Dijkstra, CM berinisiatif untuk membangun sebuah gereja baru, yang peletakan batu pertama pembangunan gereja Kristus Raja dilakukan pada tahun 1956. Setahun kemudian, tahun 1957, gereja Kristus Raja diberkati dan diresmikan oleh Mgr. Drs. J.A.M. Klooster, CM. Setelah gedung gereja Kristus Raja yang baru resmi digunakan, maka pada tanggal 1 Juli 1958 gereja lama oleh Romo E. van Mensvoort, CM. dijadikan gedung sekolah SMPK untuk putra dan diberi nama “St. Stanislaus”. Letaknya berdampingan dengan komplek SD Theresia I, Jl. Residen Sudirman No. 5 Surabaya.
* Vikaris episkopalis atau yang lazim di Indonesia disingkat dengan sebutan Vikep adalah jabatan yang diberikan kepada seorang pastor atau uskup auksiliari atau uskup koajutor dalam suatu keuskupan untuk mewakili sebagian tugas-tugas dan wewenang uskup dalam suatu wilayah yang lebih sempit atau untuk kelompok yang spesifik.
* Prefektur Apostolik adalah bentuk otoritas rendah untuk suatu wilayah pelayanan dalam Gereja Katolik Roma yang dibentuk di sebuah daerah misi dan di negara yang belum memiliki keuskupan.
* Prefek Apostolik adalah seorang imam misionaris di daerah misi yang ditunjuk Paus untuk memimpin suatu Prefektur Apostolik
