Eldste omtale av en kirke på (gnr. 8) Kiberg er i 1589 (Kyberg, Thr.R. 92). Trædal (2008:255) ser ut til å mene at middelalderkirken skal ha stått litt lenger øst, der nåværende skolebygning står (bnr. 105), mens kirken bygd 1667 skal ha stått ”på det som nå utgjør vestre banehalvdel” av fotballbanen (bnr. 14).
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.