Pematangsiantar merupakan pusat Daerah Simalungun yang menjadi bagian dari Gouvernement van de Ookust (Gubernemen Pantai Timur). Karya Zending Protestan di kalangan Orang Batak Simalungun sudah dimulai sejak tahun 1901. Akan tetapi masih banyak di daerah Simalungun ini belum menjadi Kristen. Alasannya adalah mereka sudah menjadi Islam dan pewartaannya tidak sampai ke pedalaman. Misi Katolik memperoleh kesulitan larangan Pemerintah Hindia Belanda dalam Buku Hukum pasal 123 (sesudah tahun 1952 tahun 177) yang mengatakan : “Guru-guru Kristen, imam-imam dan pendeta-pendeta” bila hendak masuk suatu daerah untuk melaksanakan tugas harus lebih dahulu mendapat izin dari Gubernur Jendral. Kalau tugas mereka dianggap dapat menggangu keamanan suatu daerah, maka izin masuk mereka dapat dicabut oleh Gubernur Jendral.Terumata “dobel-zending” dilarang (sekaligus Misi Katolik dan zending protestan)”.
Misi di Pematangsiantar dan sekitarnya sudah mulai sebenarnya sejak Juli 1929 oleh permintaan yang diajukan oleh 120 orang Katolik di sekitar Pematangsiantar. Kerohanian umat di sini dilayani oleh Pastor Aemilius Van Der Zanden dari Medan. Pada waktu itu timbul usaha untuk mengajukan usul kepada Mgr. Mathias Brams agar di Pematangsiantar dibangun sebuah gereja dan ditempatkan seorang Pastor untuk memimpin umat di daerah ini. Pada bulan Juni 1931 diperoleh izin seorang imam Katolik menetap di Pematangsiantar. Akan tetapi, izin tersebut disertai dengan larangan memperluas ajaran agama di luar tempat kedudukan. Stasi Batak pertama didirikan di dekat Pematangsiantar yaitu Laras di wilayah perkebunan, pada tahun 1931.
Pada tanggal 3 Juli 1931, P. Aurelius Kerkers memulai karyanya di Pematangsiantar. Dalam perkembangan selanjutnya, ternyata disadari tidak mungkin mentaati larangan pengajaran agama Katolik di daerah lain. Ketidakmungkinan tersebut bukan terutama dari pihak pastornya, tetapi juga oleh karena semakin banyak permintaan dari pihak orang Batak agar Katolik diperkenalkan. Di Pematangsiantar, pada 1 Januari 1932 umat Katolik sudah ada sebanyak 203 orang: 174 orang Eropa, 19 orang Batak (yang dipermandikan di Medan), 5 orang Cina, 5 orang Jawa. Pada 1 Juni 1932, dibukalah sebuah Hollands Inlandse School. Pada akhir 1932 diajukan permohonan izin bagi karya misi di daerah Simalungun dengan bertolak Pematangsiantar. Tanggal 17 Februari 1933, datanglah jawaban positif. Pada tahun yang sama, yakni melalui surat tertanggal 12 Agustus 1933, akhirnya keluarlah izin umum yang memperbolehkan penyebaran pengajaran keagamaan. Maka dibentuklah beberapa Stasi-Stasi bantuan pertama yakni, Laras, Pantoan, Tanah Djawa, dan Panei.
Penyebaran misi Katolik di Pematangsiantar semakin mantap dengan diangkatnya seorang Katekis yang membantu penyebaran ke- Katolikan-an, yakni Kenan Hutabarat. Bersama Katekis ini, karya misi semakin mantap. Pastor Aurelius Kerkers melihat jumlah umat semakin banyak. Pada saat itu dilihat bahwa sudah saatnya membangun fasilitas yang sungguh berguna. Pembangunan gereja, sekolah, pastoran dan susteran (seperti sekarang ini) mulai dilakukan. Gereja tersebut diberkatinya tahun 1934.
Beberapa catatan tentang perkembangan misi di Pematangsiantar ini perlu ditambahkan. Pastor Aurelius Kerkers kemudian hari dibantu oleh Pastor Elpidius Van Duinhoven yang tiba di Pematangsiantar pada tanggal 16 Februari 1934. P. Elpidius Van Duinhoven dengan sangat gigih mendirikan beberapa Stasi baru. Dia mendirikan Stasi baru di Sawah Dua-Panei tanggal 1 Januari 1936. Stasi ini menjadi pusat kegiatan untuk daerah Panei dan sekitarnya: Tigadolok, Sidamanik, dan sampai ke Saribudolok yang berdiri sejak 30 Agustus 1938.
Pada masa pendudukan Jepang, kegiatan misi lumpuh. Hanya para Suster berkebangsaan Jerman di Balige yang boleh tinggal. Akan tetapi, masih ada keuntungan besar lain yakni karena P. Marianus van den Acker selaku pemelihara rohani para Suster tersebut tidak ikut ditawan. Pada kesempatan itulah dia membentuk Badan Pimpinan Gereja selama masa sulit itu dengan mengangkat beberapa katekis. Yang menjadi Ketua Badan Pimpinan Gereja tersebut adalah Y. B. Panggabean sekaligus katekis kepala di Balige. Di Wilayah Simalungun, K. Hutabarat menjadi katekis kepala di Pematangsiantar, P. Datubara (Saribudolok).
Pada tahun 1965, karmelit membangun biara di Pematangsiantar yakni Seminari Agung (Fakultas Teologi Karmel). Alasan perpindahan pusat pendidikan Karmel dari Malang ke Pematangsiantar adalah alasan keamanan, yakni terjadinya ketegangan pasca peristiwa “G30S/PKI” di Jawa. Pimpinan Karmel saat itu melihat bahwa Sumatera merupakan tempat yang aman sekaligus tepat, untuk kelanjutan pendidikan para fraternya.
Wacana kehadiran para Karmelit di Pematangsiantar disambut dengan baik. Umat dan lembaga-lembaga Gereja memberikan dukungan. Yayasan Cinta Rakyat turut memberi dukungannya yang sangat berharga, karena mereka memperboleh Seminari Agung Karmelit tersebut didirikan di atas tanah mereka. Dalam surat keterangan dukungan Yayasan Cinta Rakyat, dituliskan demikian. “Ketua Pengurus Jajasan Tjinta Rakjat Pematangsiantar, menjatakan, tidak berkeberatan bahwa Badan Pengurus Geredja Katolik dan Amal di Pematangsiantar akan mendirikan Geredja dan Seminari Agung di tanah kami yang terletak disebelah Kebun Siantar State didekat Djalan Bali dan Djalan Sisingamangaradja”. Berdasarkan kutipan di atas, bisa dikatakan bahwa sejak awal telah direncanakan juga sekaligus pembangunan Gereja untuk umat. Bangunan Karmel inilah yang digunakan umat.
Di sekitar bangunan ini sudah ada beberapa umat Katolik. Mereka beribadat di rumah-rumah umat. Berdasarkan Buku Baptis (LB) paroki, kita ketahui lebih terang bahwa sudah ada pembaptisan pertama di tiga titik daerah: Jl. Bali (20 Februari 1958), Martoba (1 November 1964), Bah Kapul (31 Mei 1958). Maka dengan kehadiran Karmel ini umat disekitarnya juga mengikuti kebaktian di gereja biara (sejak Juni 1966). Stasi St. Yusup Jalan Balipun berdiri. Pembaptisan pertama di Gereja ini sesudah kehadiran para Karmelit pada tanggal 16 Oktober 1966. Gereja ini seringkali dituliskan (dikenal) dengan nama Gereja Karmel atau Gereja St. Jusup Karmel.
Karmel juga sekaligus mendirikan Sekolah Dasar, yang diberi nama Sekolah Dasar Karmel 1. Tidak banyak informasi yang diperoleh tentang hal ini. Misalnya, apakah SD Karmel 1 ini yang kemudian menjadi SD Cinta Rakyat saat ini (cikal bakal?). Keterangan keberadaan SD Karmel ini sangat terang dari Surat Permohonan kepada Walikota Pematangsiantar tentang memohon pembuatan Jalan Karmel, untuk jalan yang menghubungkan Jalan Bali dengan Kompleks biara, gereja dan sekolah. Pada no. 2 dikatakan demikian, “ S.D jang terletak di udjung jalan itu adalah S.D Karmel 1 yang diurus oleh pastor-pastor karmel”.
Sesudah Stasi baru St. Yusup-Jl. Bali berdiri (1966), Badan Pengurus Gereja dan Amal Katolik mulai memikirkan pemekaran paroki Jl. Sibolga tahun 1967 Paroki St. Laurensius-Jl. Sibolga dimekarkan. Pada tahun 1968, Paroki Jl. Sibolga dimekarkan kemudian dengan mendirikan Paroki St. Fransiskus-Jl. Medan. Demi efektivitas pelayanan, Paroki Jl. Sibolga terus dimekarkan dengan membentuk paroki-paroki baru: Paroki Kristus Raja-Perdagangan (1970), Paroki Kristus Raja Tanah Jawa (1976), Paroki Saribudolok, Paroki Parapat. Selain Stasi Jl. Bali sendiri, Stasi Bah Kapul diserahkan pada pelayanan Karmelit. Dengan diserahkan kepada pelayanan Karmelit, akhirnya muncul gagasan baru, yakni mendirikan gereja permanen. Maka, pada tahun 1968, pembangunan gereja di Bah Kapul- Sibatubatu mulai digagas. Pastor Paroki saat itu, Pastor Koning, O.Carm, segera mengajukan permohonan pembangunan gereja baru kepada Bupati Simalungun.
Pada tahun 1969, Stasi Martoba kemudian diserahkan kepada pelayanan para Pastor Karmelit. Baptisan di Stasi ini dicatat di Paroki St. Laurensius terakhir pada tanggal 29 juni 1969. Sesudah tanggal ini, segala yang berhubungan dengan Stasi ini dicatatkan di Paroki St. Jusu-Jl. Bali. Maka, disimpulkan bahwa sampai tahun 1969, Paroki St. Jusup memiliki tiga Stasi: Jl: Bali (Stasi Induk), Bah Kapul, dan Martoba. Pada tahun 1970, Para Karmelit segera meninggalkan pematangsiantar pimpinan Karmel melihat bahwa pemberontakan PKI tidak lagi merupakan ancaman serius. Alasan keamanan dirasa tidak tepat lagi menjadi alasan membagi dua tempat pendidikan frater. Disisi lain, perpindahan ini juga dipengaruhi kerumitan internal tentang program pendidikan para frater mereka. Misalnya, bagaimana menyesuaikan program kuliah dengan Seminari Agung di Pematangsiantar.
Bagaimana dengan keberadaan gedung biara yang besar tersebut? Setelah theologicum Karmelit pindah kembali ke Malang pada akhir tahun 1970, Ordo Karmel ingin menjual gedung mereka. Gabungan kongregasi suster-suter berpendapat bahwa gedung tersebut cocok untuk pusat pendidikan dan rumah retret. Namun, karena gedung itu terlalu besar untuk hal dimaksud, para suster mengusulkan agar pihak keuskupan membeli gedung tersebut dan menyewakannya kepada suster. Akan tetapi, akhirnya sebagian besar gedung tersebut dibeli oleh gabungan suster-suster. Maka pada tanggal 6 juli 1970, mulailah para suster tinggal disana. Gedung besar tersebut akhirnya digunakan sebagai Pusat Pembinaan Para Biarawan/wati, sampai akhirnya mereka membangun pusat yang baru di Sinaksak, Pematangsiantar tahun 1993.
Maka sejak saat itu, gedung tersebut difungsikan untuk dua hal sekaligus, yakni sebagai kantor paroki (Sekaligus Pastoran), dan tempat pembinaan para suster (Bina Samadi). Maka segala hal yang menyangkut tentang gedung tersebut, perbaikan, batas tanggungjawab masing-masing pihak, senantiasa diperbaharui dalam dan dengan surat perjanjian antara pihak P3B (Pusat Pembinaan Para Biarawan/wati). Hanya beberapa kamar saja yang digunakan untuk paroki, terlebih sebagai kantor paroki.
Bagaimana pelayanan Paroki? Sejak para Karmelit meninggalkan Paroki St. Joseph, dan kehadiran P3B disana, paroki ini dilayani oleh Pastor Kapusin P. Marianus van den Acker, yang diangkat menjadi rektor pembimbing para suster, beliau sekaligus juga menjadi pastor paroki. Pada tahun 1973, Pastor Clemens Hamers, diangkat menjadi pastor paroki. Akan tetapi, beliau baru pindah pada bulan Maret 1974 ke Pastoran St. Joseph, sesudah gedung tersebut ditata kembali penggunaannya. Gereja tersebut dibuat dinding baru, sehingga sebagian menjadi kapel para suster, dan sebagian lagi menjadi gereja paroki.
Dari beberapa arsip surat menyurat yang masih tertinggal, diketahui adanya perkembangan jumlah umat yang pada akhirnya gereja yang ada pada saat itu tidak cukup untuk menampung umat. Ketika P. Gonzalvus Snijders sebagai Pastor Paroki (1976-1984), dia beberapa kali mohon kepada pihak Keuskupan untuk segera memperbesar gereja atau memperbesar/membangun gereja baru (tahun 1977, 30 Jan 1980, 27 Maret 1980 ). Dalam surat-surat permohonan tersebut P. H Snijders menyebutkan beberapa alasan pengajuan permohonan tersebut: Perpindahan SPG tahun 1977 sehingga gereja tidak cukup untuk menampung umat, perluasan kota dan pertambahan jumlah penduduk. Pembangunan Gereja tersebut baru bisa dimulai pada tahun 1983. Pada tahun 2005, digagas juga didirikan gereja baru di depan gedung paroki/gereja saat ini. Gedung gereja baru tersebut telah berdiri besar, gagah dan unik dan sudah diresmikan April 2012 dan sejak itu sampai sekarang umat beribadah di dalamnya dan gedung gereja lama dipakai sebagai aula paroki.
Paroki Jl. Bali kemudian menjadi paroki besar. Pada tahun 1987, stasi-stasi ke arah sisi kanan parapat sampai ke arah Tigaras, menjadi bagian (stasi) Paroki Jl. Bali. Mengapa paroki Jl. Bali menjadi paroki “raksasa” ?. Dugaan P. Ari van Diemen adalah karena semua stasi tersebut dari segi wilayah (secara praktis) lebih cocok dimasukkan menjadi bagian dari Paroki St. Joseph-Jl. Bali. Dugaan lain menurutnya adalah karena paroki sendiri memiliki gedung yang sangat luas, dan sangat cocok untuk tempat pembinaan. Paroki Jl. Sibolga menjadi paroki tanpa Stasi lebih merupakan karena pertimbangan jumlah umat. Pada tanggal 11 juli 2010, Paroki “raksasa” ini dimekarkan dengan mendirikan Paroki Tiga Dolok meliputi Tiga Balata dan Tiga Dolok. Penggembalaan paroki ini diserahkan kepada para Saudara Dina Konventual.
