Gereja Balung terletak di batu 17 (27KM) sebelah timur, Tawau. Kawasan ini ialah Skim Rancangan Penempatan dengan bantuan Kerajaan. Sebilangan besar penduduknya ialah petani. Disebabkan tanahnya yang subur, ianya sesuai untuk tanaman koko dan tanaman-tanaman yang lain. Pada Pada awal tahun 1960, sebilangan besar orang Cina yang telah ditempatkan adalah dari kawasan pedalaman. Mereka datang dan membersihkan hutan rimba dan memulakan tanaman pokok getah dan kelapa sawit. Ramai di antara penduduk adalah kaum Bumiputera dan hanya sebilangan kecil orang Cina.
Dalam pertenganhan 1961, Dn James Pung, bersama dengan Sdra Chung Moi Hiong, Sdra Ng Kiong dan 120 orang anggota Gereja Sungai Paal yang telah dijawat oleh Lembaga Kemajuan Tanayh Sabah (SLDB) berpindah ke Balung. Dalam masa lapang, mereka tidak melupai kewajipan terhadap Tuhan. Oleh itu, mereka telah menggunakan rumah kediaman Dn Pung sebagai Rumah Doa dan berhimpun setiap minggu di situ untuk mengadakan Kebaktian Sabat. Pada penghujung tahun 1963, Dn Gaius Leong dan 6 keluarga lain seramai 40 orang pemercaya berpindah dari Beaufort ke Balung. Akibatnya, bilangan pemercaya meningkat ke 70 orang. Satu mesyuarat diadakan oleh Dn Pung untuk menubuhkan jawatankuasa yang terdiri daripada Penguasa Hal Ehwal Agama : Dn James Pung; Timbalan : Gaius Leong; Hal Ehwal Am : Pung Ming Fook; Bendahari : Leong Fook On dan Setiausaha: Chung Moi Hiong.
Selepas penubuhan gereja, dengan berkat Tuhan, banyak tanda ajaib dan mujizat berlaku. Ramai kaum Murut yang mencari Kebenaran menerima rahmat yang berkelimpahan daripada Tuhan Yesus Kristus. Penyakit yang tidak boleh disembuhkan oleh doktor telah disembuhkan selepas menerima pembaptisan. Saksian yang agung adalah daripada Sdra Mingau bin Abang. Dia mengidap sesuatu penyakit ddan tidak dapat berjalan. Dia telah sembuh selepas menerima pembaptisan bersama dengan 130 orang lain.
Selepas itu, bilangan anggota gereja semakin meningkat dan Rumah Doa tidak dapat lagi menampung bilangan mereka. Dalam pertengahan 1965, Ibu Gereja telah mengirim Dn Titus Yong untuk membuat lawatan penginjilan di situ. Dia telah sedar bahawa sebuah gereja yang sesuai harus didirikan untuk menampung bilangan anggota yang semakin meningkat dan seterusnya mengadakan satu mesyuarat agung. Keputusan telah dibuat untuk mendirikan sebuah gereja dengan secepat mungkin. Pada permulaannya tabung kewangan bangunan ditubuhkan. Dn Pung telah diberi mandat untuk menghubungi Lembaga Kemajuan Tanah Sabah untuk mendapatkan satu tapak gereja. Disebabkan kekurangan kewangan dan tenaga untuk mengendalikan kerja Tuhan, Tuhan telah mengatur Dn Thomas Chew dan keluarganya berpindah dari Sungai Paal ke Balung untuk mencari nafkah hidup. Dn Chiew adalah seorang kontraktor bangunan kecil. Dengan kehadirannya, masalah telah diatasi. Kerja untuk membina gereja bermula dalam Ogos 1967. Bangunan ini yang boleh menampung seramai 200 orang telah siap dibina pada 10 Disember. Pentahbisan Gereja diadakan pada 19 Disember 1967. Bermula dari 1968 kemudiannya, Penguasa Gereja sehingga sekarang ialah Dn Gaius Leong. Sejak dari itu, Pendidikan agama telah diadakan.
Pada 1981, satu mesyuarat agung telah diadakan untuk membincang pembinaan bangunan gereja tetapi untuk pembangunan gereja di masa hadapan. Syukur kepada Tuhan, pada bulan Oktober 1985, pembinaan dijalankan dengan licinnya. Pada awal Disember 1986, bangunan gereja dua tingkat yang berharga $130,000.00 yang berukuran 23.2cm x 12.2cm (76′ x 40′) telah siap dibina. Bermula dari 19 hingga 21 Disember 1986, satu Pentahbisan Gereja dan Kebaktian Kebangunan Rohani diadakan. 378 orang telah mengambil bahagian dalam Perjamuan Kudus. Dalam kebaktian, terbang di udara dalam doanya. Kemudian, ia melihat satu cahaya hampir sama dengan bulan bersinar dengan terang ke atas bangunan dan satu tangga menuju ke Syurga di hadapannya.
Pada penghujung 1986, bilangan anggota gereja Balung adalah 128 orang. Selain dari kebaktian Sabat, kebaktian malam juga diadakan pada Hari Rabu dan Perhimpunan Belia pada malam Hari Ahad. Pendidikan Agama dibahagikan kepada dua bahagian iaitu Bumiputera dan Cina. Bahagian Bumiputera mempunyai 2 kelas manakala bahagian Cina pula mempunyai 5 kelas. Jumlah murid ialah 70 orang dan guru seramai 17 orang. Penguasa Pendidikan Agama ialah Sdra Pung Yit Siong. Jawatankuasa Gereja sekarang adalah terdiri daripada:-
Hal Ehwal Agama : Gaius Leong, James Pung (Naib)
Hal Ehwal Am : Pung Yit Siong, Pung Ket On (Pembantu)
Bendahari : Ng Siew Poh, Chin Hin (Pembantu)
Setiausaha : Hiew Ming Chung, Ng Hao Poh (Pembantu)
Ahli : Pung Min Fook