Gereja St Martinus yang menjadi permulaan terbentuknya Paroki St Klement I sudah cukup lama berdiri.
Pada awalnya tahun sekitar 1960 an beberapa keluarga umat Katolik Sepinggan yang merupakan Anggota TNI AU beribadah secara oikumene dengan umat kristiani yang lain. Jumlah umat semakin berkembang dari tahun 1965 sampai dengan 1970 an baik yang merupakan anggota TNI AU maupun sipil masyarakat di area sepinggan dan sekitarnya mereka beribadah dari rumah ke rumah. Keluarga dari TNI AU antara lain Bpk AV Suratman , Bpk Suprapto dan keluarga dari Sipil Bpk Yohanes Dalwadi .
Lalu ada keinginan dari umat yang semakin berkembang untuk memiliki gereja sendiri dan mencoba mencari lahan yang kosong namun terkendala pada kala itu cukup sulit mendapatkan lahan. Dari umat yang merupakan anggota TNI AU lalu menawarkan area kosong yang berada di lingkungan TNI AU , dan umat mengajukan untuk menjadi lokasi di dirikan gereja dengan meminta ijin dari Pusat TNI AU yang ada di Makasar. Setelah mendapat ijin sekitar tahun 1975 , kmudian umat mengurus proses perijinan untuk pendirian gereja, prosesnya cukup berjalan lama dari tahun 1975 sd 1977 krna ada minimal jumlah umat sipil harus minimal 25 KK, semntara saat itu jumlah KK sipil belum mencukupi tapi jika digabung dengan keluarga Katolik di TNI AU ada 30 KK. Dengan usaha dari Bpk AV Suratman akhirnya bisa diperoleh ijin untuk mendirikan gereja. Itulah lokasi yang sampai saat ini masih digunakan sebagai gereja.
Pembangunan fisik gereja dibangun tahun 1977 dengan biaya swadaya dari kolekte umat, donatur dan dana dari Paroki St Theresia Prapatan dangan ketua panitia pembangunan waktu itu yaitu Bpk Bambang Setiaji . Akhirnya Gereja bisa berdiri di tahun itu juga. Pastor yang melayani pada waktu itu adalah Pastor Martinus Van Der Berg. Dari hasil pertemuan umat di sepakatilah nama gereja St Martinus seprti nama pastor yang melayani saat itu, dan resmi terbentuklah Stasi St Martinus Sepinggan yang merupakan bagian dari Paroki St Theresia Prapatan tahun 1977 tersebut.
Sejak berdirinya Gereja dari tahun 1977 sampai tahun 2002, jumlah umat semakin berkembang dari awalnya hanya 30 an KK menjadi hampir 600 an KK. Dari umat dan pastor paroki kala itu di tahun 2000 yaitu Pastor Siprianus, Msf memandang perlu berkembangnya Stasi menjadi Paroki mandiri. Lalu Pastor beberpa pengurus antara lain Bpk Sunardi (Alm), Bpk YP Paidi, Bpk Suratmin mengurus pembentukan paroki baru, Untuk nama paroki awalnya diusulkan menggunakan nama yang sama dengan nama gereja yaitu St Martinus namun ada kekhawatiran umat jikalau ada perubahan status paroki di kemudian hari bisa menghilangkan nama gereja St Martinus, oleh karena itu diputuskan nama Paroki berbeda dengan nama gereja yaitu dipilih nama Paroki St Klement I, Paroki di resmikan terbentuk pada tanggal 10 Februari 2002.