Sejarah berdirinya Gereja Katolik Paroki Santa Maria Tak Bercela Ngagel di Surabaya secara ringkas dapat diuraikan sebagai berikut : pada tahun 1958 merupakan titik awal tonggak berdirinya paroki SMTB yang dikenal dengan paroki Ngagel. Pada saat itu didaerah Ngagel dan sekitarnya sebagian besar masih merupakan persawahan dan ladang, namun pada sebagian area telah dimulai pembuatan kapling – kapling perumahan.
Keuskupan Surabaya dengan pandangan jauh kedepan mempergunakan kesempatan tersebut ikut membeli beberapa kapling tanah untuk mempersiapkan pendirian gedung gereja beserta rumah pasturan dan gedung sekolah dimasa mendatang. Dan situasi politik pada masa itu mendorong beberapa pihak tertentu untuk bertindak diluar hukum, yaitu dalam waktu singkat daerah ini diserbu oleh ratusan keluarga dengan mendirikan rumah – rumah secara liar; termasuk pendirian bangunan liar diatas lahan yang telah dibeli Keuskupan Surabaya tersebut.
Akan tetapi pembangunan perumahan resmi didaerah ini dapat berjalan dengan baik, sehingga bertambah umat Katolik yang berdian didaerah ini. Oleh karenanya mulai dirasakan oleh Keuskupan akan pelayanan dan pembinaan iman Katolik untuk kebutuhan umat Katolik didaerah Ngagel dan sekitarnya yang pada waktu itu masih merupakan Wilayah 5 dari Paroki Hati Kudus di Darmo.
Maka untuk meningkatkan karya pelayanan dan pembinaan iman Katolik para umat di Ngagel, kemudian Keuskupan menyediakan sebuah rumah biasa yang bertempat di Jalan Ngagel Jaya Tengah VI / 17 Surabaya untuk dipergunakan sebagai tempat ibadah kebaktian darurat dan diresmikan serta diberkati untuk penggunaannya pada tanggal 5 Nopember 1967. Sedangkan tugas pelayanan dan pembinaan untuk pertama kali dipercayakan kepada Pastur M. Van Driel CM; yang kemudian terakhir dipercayakan kepada Pastur H.A. Massen CM yang dipindahkan dari Blitar ke Surabaya.
Kemudian mengingat perkembangan jumlah umat pada waktu itu mulai banyak maka dirasakan perlunya membangun rumah ibadah yang lebih besar. Pada tanggal 9 April 1968 dimulai penggalian pondasi diatas tanah kosong yang telah tersedia tersebut. Dan pada tanggal 8 Desember 1968 bertepatan dengan pesta nama “Santa Maria Tak Bercela”, gereja baru yang merupakan sebagian dari bangunan SDK “Santa Clara” di Jalan Ngagel Madya nomer 1 Surabaya, diberkati oleh Mgr. J.A.M. Klooster CM selaku Uskup Surabaya.
Gereja tersebut masih bersifat sementara dengan status Stasi dari Paroki Darmo yang mempunyai daya tampung sekitar 350 umat. Dan karena belum ada rumah pasturan, maka gembala pastur H.A. Massen CM masih tinggal di Pasturan Paroki Darmo; dan pelayanan beliau pada umat di Ngagel merangkap bertugas pada Stasi Sidoarjo.
Bersamaan dengan pembangunan gereja ini, mulai dibangun pula gedung TK dan SD yang kemudian kepengurusannya diserahkan kepada para suster dari Kongregasi Missonaris Claris yang kemudian menjadi dikenal dengan sekolah “Santa Clara”.
Sementara jumlah umat Katolik didaerah Ngagel dan sekitarnya berkembang pesat jumlahnya, maka Pastur H.A. Massen CM mengusulkan agar daerah baru ini sebagai suatu paroki baru, yang disetujui oleh Mgr. J.A.M. Klooster CM pada tanggal 9 April 1969 sebagai Paroki Santa Maria Tak Bercela dengan Pastur Kepala Paroki yang pertama adalah Pastur H.A. Massen CM. Berbekal kemauan keras dari Pastur H.A. Massen CM, maka pembangunan rumah pasturan dapat mulai dibangun dan pada tanggal 20 April 1970 diberkati penggunaannya oleh Mgr. A.J. Dibyokarjono pr, Vikaris Jenderal Keuskupan Surabaya pada saat itu.
Pada tanggal 19 September 1971 dimulai penggalian pondasi untuk pembangunan gereja tahap I dengan pembeayaan dari sebagian digali dari swasembada umat dengan cara mengadakan bazaar amal dan usaha – usaha lainnya, sebagian lainnya dari sumbangan para dermawan dan juga dari Walikota Surabaya melalui Sub Direktorat Kesejahteraan Rakyat (Kesra); dan sebagian lagi dari dana yang berhasil dikumpulkan oleh Pastur H.A. Massen CM selama cuti di Belanda. Maka pembangunan gereja tahap I dapat dilaksanakan dengan singkat. Dan pada tanggal 24 Desember 1972 – gereja tahap I diberkati penggunaannya oleh Uskup Surabaya Mgr. J.A.M. Klooster CM dan pengguntingan pita dilakukan oleh Ibu Soekotjo, istri Walikota Surabaya. Gereja ini mempunyai daya tampung sekitar 700 umat.
Dikarenakan daya tampung gereja sudah tidak dapat menampung umat yang melakukan ibadah disana, maka rencana pembangunan gereja tahap II mulai disusun walaupun dana belum cukup tersedia dari anggaran yang direncanakan.
Dengan modal tekad yang kuat pada tanggal 23 Oktober 1974, para umat mulai menggali pondasi untuk bangunan gereja tahap II. Segala daya dan dana dikerahkan dengan penuh semangat pengabdian; walaupun penuh dengan tantangan yang harus dihadapi. Namun dengan pertolongan dari Bunda Maria pelindung paroki, pembangunan pondasi dan dinding – dindingnya dapat diselesaikan. Karena kelelahan maka Pastur H.A. Massen CM terpaksa dengan berat hati meninggalkan pekerjaan yang belum selesai tersebut untuk berobat di Belanda karena penyakit yang dideritanya.
Biarpun ditinggal gembalanya, dengan adanya kerja keras para panitia pembangunan beserta umat yang sadar akan tanggung jawabnya maka pembangunan gereja tetap diteruskan sehingga kerangka atap dapat dipasang.
Sekembalinya dari berobat, pastur H.A. Massen CM langsung melanjutkan pembangunan gereja tahap II dan akhirnya dengan pertolongan Bapa Yang Maha Kasih serta bantuan tak terhingga dari para umat paroki Ngagel; pembangunan gereja tahap II dapat diselesaikan dan diberkati oleh Mgr. J.A.M. Klooster CM. Upacara peresmian dengan pengguntingan pita yang dikukuhkan oleh seorang Pejabat Kotamadya Surabaya dan disaksikan oleh Bimas Katolik, Kanwil Depag Dati I Jawa Timur.
Gedung gereja tahap II kemudian dipergunakan sebagai Gedung Pertemuan dan dapat disatukan dengan gereja tahap I; sehingga merupakan ruangan ibadah kebaktian yang dapat menampung sekitar 1.500 umat dengan balkon keliling kiri – kanan – belakang.
Gedung gereja “Santa Maria Tak bercela” telah selesai dibangun namun penyempurnaannya untuk melengkapi segala persyaratannya, masih banyak harus dikerjakan. Oleh karenanya Dewan Paroki serta Yayasan Gereja dan Amal dengan bantuan umat paroki setapak demi setapak tetap melanjutkan pengerjaan penyempurnaannya.
Pada 4 Maret 1996 pastor Julius Haryanto CM (1994-1999), selaku Kepala Paroki mengundang Dewan Paroki dan banyak orang yang nantinya terpilih sebagai Panitia Renovasi Gereja. Dalam pertemuan tersebut pastor Haryanto menggagas penambahan sebuah menara untuk lonceng yang dimiliki sejak beberapa tahun sebelumnya, penggantian atap seng yang sudah tua, ventilasi yang kurang, umat bertambah, silau karena matahari sore dan banjir yang sudah beberapa kali terjadi. Perlu pula adanya peremajaan pada tampak gereja. Tugas panita adalah memikirkan, merencanakan dan melakukan reovasi serta menggali dana baik dari umat maupun dari donatur. Melalui banyak rapat dan perdebatan perencanaan gambar mengalami banyak perubahan berkali kali hingga akhirnya lahirlah design gambar gereja ber-basement dan disepakati untuk mewujudkannya. Namun akhir 1997 kondisi ekonomi mulai tidak menentu sehingga akhirnya gagasan untuk mewujudkan gereja berwajah baru itu terpaksa ditangguhkan. Penangguhan tanpa batas waktu.
Pada permulaan tahun 2000 saat pastor C.B. Senti Fernandez Pr (1990-2002) menjabat sebagai Kepala Paroki gagasan untuk merenovasi gereja muncul kembali setelah cukup lama vacum. Panitia renovasi yang sudah terbentuk sebelumnya dipanggil kembali untuk segera merenovasi dengan mengikuti petunjuk baru dari bapak uskup. Setelah ijin dari Bapak uskup keluar, kemudian dilakukan pembongkaran bangunan gedung gereja. Selama renovasi umat harus beribadat di balai paroki (lantai 1). Sementara design gambar gereja sudah tidak mengikuti design lama tetapi sudah dibuatkan gambar yang sama sekali baru. Panitia menggunakan sistem tender, baik untuk tahap struktur maupun untuk tahap penyelesaian.
Gedung gereja yang baru ini diberkati oleh Mgr. J. Hadiwikarta, uskup surabaya, tepat pada ulang tahun paroki, 8 Desember 2001 dalam perasaan ekaristi yang dihadiri oleh para romo romo yang pernah bertugas di sini baik sebagai pastor Kepala maupun sebagai pastor rekan.
Untuk membantu umat mewujudkan iman dalam hidup menggereja, saat pastor A. Andri Noertjahja EW Pr (2002-2007) menjabat sebagai pastor kepala, dilakukan pembangunan sarana penunjang fasilitas gereja. Pembangunan itu meliputi pembangunan gedung serba guna 3 lantai, renovasi balai paroki lantai 1 dan lantai 3, renovasi pastoran lama, pembangunan griya Maria, pembangunan rumah genset dan sebagainya.