Sejarah paroki kurang jelas hingga saat ini. Sejarah berikut ini dirangkai dari sejumlah pranala di Google.
Berdirinya gereja dan paroki dimulai oleh misionaris OFMCap seiring dengan terbentuknya paroki Tg. Balai tahun 1947. Gerejanya sendiri mungkin berdiri lebih awal lagi sekitar tahun 1927 dan mungkin pernah dipugar mengingat pada masa itu hingga tahun 1980an terdapat kesusteran yang melayani pengobatan dan pendidikan.
Paroki sendiri setelahnya beralih ke ordo Serikat Xaverian hingga salah satu ordo dari AS dan dilanjutkan Imam Projo hingga tahun 1993. Pada masa peralihan dari Imam Projo ke Karmelit (O. Carm) dari tahun 1993-2000 sempat terjadi kekosongan imam paroki. Misi O.Carm sampai hari ini masih tertera pada bangunan sekretariat “Zelo zelatus sum pro Domino Deo exercituum.” yang artinya "Aku bekerja segiat-giatnya bagi Tuhan, Allah semesta alam", 1 Raja-raja 19: 10.
Sejak 2-3 tahun lalu, paroki telah beralih dari O.Carm ke SS.CC yang kemungkinan hanya sementara hingga ada ordo yang dirasakan lebih cocok.
Paroki Tanjung Balai Asahan adalah paroki yang unik dengan umat dari beragam suku dan jarang bertahan lama di lingkungan kotanya. Pelayanan ke stasi-stasi juga menjadi tantangan bagi Imam karena harus menggunakan sepeda motor hingga pelosok. Paroki Tanjung Balai Asahan adalah paroki tua dan merupakan cikal bakal paroki di sekitar Labuhan Batu, seperti Kisaran, Aek Kanopan, dan Aek Sabara.
Sekolah Katolik Tritunggal Tg. Balai yang terletak di belakang gereja adalah sebuah karya pendidikan dari para Imam yang terkenal bagus, bermutu dengan kedisiplinannya.
Gereja St. Mikael yang merupakan salah satu gereja tertua di Sumatera Utara bahkan di Indonesia Bagian Barat.
Saat ini Romo yang bertugas sebagai Administrator Paroki adalah Pater Yose (RP Yosef Riang Hepat SS.CC) yang bisa dihubungi setiap saat di pastoran.{{sect-stub}}
