Menurut informasi dari masyarakat, gereja ini awalnya dibangun tahun 1928 di pesisir Pulau Asei Besar dengan konstruksi kayu yang sederhana. Namun pada masa Perang Dunia II, saat perebutan wilayah Pasifik antara Pasukan Sekutu dan Pasukan Jepang, bangunan gereja ini hancur dibom oleh Pasukan Sekutu.
Bangunan gereja ini dibangun kembali pada 1 Januari 1955 di puncak bukit Pulau Asei Besar. Masyarakat Asei membangun kembali Gereja ini dengan bantuan dari Jerman. Mengingat, misionaris Injil di Pulau Irian adalah W. Ottow Carl dan Johann G. Geissler yang berasal dari Jerman.
Bangunan ini menghadap ke arah barat, yang teridentifikasi dari letak menara lonceng, dan pintu masuk utama yang berada di sisi barat bangunan. Denah bangunan ini memanjang barat-timur. Memiliki satu ruang utama sebagai tempat ibadah jemaatnya dan sebuah ruang di sisi selatananya yang berfungsi sebagai tempat penyimpanan peralatan gereja. Di ruangan utama terdapat 10 buah tiang kayu penopang atap dengan posisi 5 tiang paralel. Mimbar pendeta berada di sisi utara ruangan yang berhadapan dengan kursi panjang untuk para jemaat di sisi selatan ruangan.
Di sebelah selatan Bangunan Gereja telah dibangun sebuah sekolah dasar oleh Yayasan Kristen Filadelfia. Dahulu di menara lonceng gereja ini terdapat lonceng perunggu yang sekarang tidak diketahui keberadaannya, dan perannya telah digantikan oleh tabung gas yang digantung di sisi barat laut dari bangunan.
