Eldste omtale av en kirke på (gnr. 8) Kiberg er i 1589 (Kyberg, Thr.R. 92). På slutten av 1500-tallet ble Kiberg beskrevet som følger: ”Suduest fra Wardöen en j miel ligger inde paa faste lande it werdt, heder Kybberyg, boer och en stor hob folck, och det ligger i Wardöe prestegield” (Storm 1895). I 1589 var Kiberg kirke anneks under Vardø og hadde prest sammen med kirkene i Vardø og Vadsø (Thr.R. 92). Middelalderkirken ble revet ca. 1667, da ny kirke sto ferdig på samme sted dette året.