Kapel St Yosef Sei Harapan.
Dikarenakan penggunaan kapela secara bergantian dengan umat Kristen lainnya, membuat Umat Katolik pada saat itu kurang nyaman dan termotovasi untuk memiliki gedung sendiri khusus bagi umat Katolik untuk beribadah dan beraktifitas.
Seiring waktu dengan pertambahan umat yang semakin banyak, Dewan Stasi St Yosef mengajukan permohonan lahan ko Otorita Batam, dan pada tanggal 10 Juli 1986 melalui Kasatlak Otorita Batam, dialokasikan lahan seluas 2.975 m2 didaerah Tiban IV.
Gereja St Yosef
Pembangunan Gereja St. Yoseph Tiban dimulai dari tahun 1987 dengan pembentukan Panitia Pembangunan sebanyak 13 orang pada tanggal 20 Maret 1987, yang dipimpin oleh (Alm)Brigjen Leo Ngali. Proses pembangunan terus dilakukan secara swadaya dan gotong royong, hingga pada 4 Maret 1991, kepanitiaan pembangunan disempurnakan dengan penambahan menjadi 22 orang dan dipimpin oleh AZ Sukardi dan pelindung adalah Kasatlak Otorita Batam dan Wakil Wali Kota Batam pada saat itu, serta Uskup Keuskupan Pangkalpinang sebagai penasihat.
Panitia menyusun rencana konkrit mulai dari pra pembangunan, desain gereja oleh Ir Freddy Tanoto, Ir Seno Prakoso dan Ir Irawan Sugiarto. Arsitektur gereja mencerminkan inkulturasi melayu dengan memakai salembayung. Peletakan batu pertama dilakukan oleh Uskup Keuskupan Pangkalpinang pada tanggal 6 Oktober 1991 ,berbarengan dengan peresmian Gereja St Petrus di Lubuk Baja Batam.
Pada tanggal 27 Maret 1994 , bertepatan dengan Minggu Palma, Gereja St Yosef Tiban resmi dipakai untuk perayaan ekaristi. Sejak saat itu aktifitas menggereja dipindahkan dari Kapel St Yosef Sei Harapan ke Gereja St Yosef Tiban.
Setelah melalui proses panjang selama 3 tahun 8 bulan, dan dengan anggaran Rp.400.000.000, panitia akhirnya menyelesaikan pembangunan tahap 1 yang meliputi ruang ibadat seluas 477m2, ruang sakristi 20m2, ruang pengakuan dosa 20m2, selasar dan kanopi 256m2 dan ruang penunjang lainnya 81m2.
Pada tanggal 30 Oktober 1994 , Bapa Uskup Keuskupan Pangkalpinang didampingi Ketua Otorita Batam Soerohadi Djatmiko dan perwakilan Walikota Batam meresmikan Gereja Katolik St Yosef Tiban.
Pertumbuhan umat di Gereja St Yosef Tiban berjalan baik, dimana pada tahun 1997 jumlah umat menjadi 300 jiwa dan untuk menunjang kegiatan kebaktian lingkungan, maka dibagi kedalam 3 kelompok berdasarkan teretorinya yaitu kelompok St Fransiskus Xaverius (wilayah Tiban Lama dan Tiban Housing), kelompok St Theresia(wilayah Sei Harapan dan Sekupang) serta kelompok St Yohanes Penginjil (wilayah Tiban 1, BTN, Palapa). Hingga tahun 2004, jumlah umat mencapai 1200 jiwa dan dimekarkan lagi menjadi 9 kelompok.
Paroki Kerahiman Ilahi
Pada tanggal 2 Desember 2007, usai mendampingi kunjungan Pastoral Nuntius/Duta Besar Vatikan untuk Indonesia Mgr. Leopoldo Girelli ke provinsi Kepri, Bapa Uskup Mgr Hilarius Moa Nurak SVD didampingi Pastor dekenat Utara/Kepri RD Lucius Poya Hobamatan mengadakan pertemuan dengan umat kuasi Paroki St Yosef Tiban di Gedung Serba Guna Tiban. Setelah mendengarkan laporan dari tim Persiapan dan Pastor Paroki St Petrus Lubuk Baja, Bapa Uskup menginstruksikan Stasi St Yosef Tiban diresmikan menjadi Paroki Keempat di Batam.
Mengenai nama pelindung paroki, Bapa Uskup menyetujui nama Kerahiman Ilahi, sesuai dengan yang diusulkan peserta rapat saat itu. Peresmian Paroki bertepatan dengan Pesta Kerahiman Ilahi, pada Minggu Paskah Kedua 30 Maret 2008, sekaligus menunjuk RD Ludgerus Lusi Oke sebagai Pastor Paroki Pertama sekaligus merangkap pimpinan KKPPMP Keuskupan Pangkalpinang. Pembangunan Gua Maria Mater Misericordiae, dan pembuatan Patung Kerahiman Ilahi dilaksanakan pada masa ini.
Pada tanggal 2019, Paroki Kerahiman ilahi mendapat anggaran dari Pemerintah utk membangun Gedung Serba Guna dan gedung Pastoran baru.
Pada Maret 2019, masa tugas RD Agustinus Tupen Belo di Paroki Kerahiman Ilahi Tiban berakhir. Serah terima jabatan pun dilakukan kepada RP Antonius Faot CS sebagai Pastor Paroki yang baru, yg mana beliau merupakan Imam dari kongregasi Scalabrinian.
Serah terima Gedung Serba Guna yang baru, dilaksanakan pada tanggal 21 November 2021, oleh Bapa Uskup Mgr Adrianus Sunarko OFM bersama Pimpinan DPRD Kota Batam Bapak Jumaga Nadeak SH dan disaksikan segenap pengurus paroki dan umat. Gedung baru tersebut didukung fasilitas pastoran baru, ruang sekretariat, aula pertemuan, dapur, ruang rekreasi Imam, dan kamar tidur imam.
Pada bulan Juli 2022, RP Heribertus Mangkur CS (Pater Ndino) didapuk menjadi Pastor Paroki yang baru. Dimasa ini, pembangunan dilanjutkan salah satunya dengan dukungan dari Bapak Johannes Kennedy Aritonang, terdapat beberapa fasilitas ditambahkan meliputi ruangan konsultasi, pertemuan, kantor pelayanan ekspatriat dan pelaut, serta ruang makan, serta lahan untuk Paroki seluas 3.258 m2 didaerah Kavling Bida, Sekupang.
Kini, Paroki Kerahiman Ilahi Tiban terus mengembangkan fasilitas gereja demi pelayanan yang lebih baik bagi umat (542 KK, 1926 jiwa).