Lokaliseringen og avgrensing av kirkestedet er uavklart, jf. Kiberg kirke 2, ID 84769 Kiberg kirkested 2. Bakgrunn for nåværende lokalisering er dette: KIBERG, gnr. 8 Kiberg (Vardø landsogn). 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. Denne ble bygd i Bergen og fraktet nord til Kiberg og satt opp der. I 1698 var Kiberg den nest rikeste av fylkets kirker. Rundt 1750 ble kirken beskrevet som "Den smukkeste kirke i hele Finmarken, som med bibelske historier var malet overalt", men i 1747 var den allerede solgt på auksjon. Nicolaissen skrev i 1891 at kirketufta midt inn på kirkegården var meget utydelig, "saavidt sees kan, er den henved 20 m lang, koret iberegnet; korets bredde har været 6 m, skibets bredde kan ikke nøiagtig bestemmes". Ved rivingen ble inventaret bestemt overført Nesseby kirke (Helland 1906:539, Trædal 2008:255f m/ref.). "Den gamle kirkegården og kirka låg på en låg strandterrasse like V for [Kibergs-] elva. Området blei først rasert av tyskerne under krigen til bunkersanlegg m.v., og dessuten utsletta til fotbollbane (bnr. 14) i [1967], slik at det nå ikke finnes noen rester tilbake. Området mellom fotbollplassen og veien er tett bebygd med hus. Jeg er ukjent med når kirkegården blei nedlagt, men den nåværende som ligger noen hundre meter lenger mot V på terrassen, blei anlagt ca. 1924. Den gamle kirkegård og tuft blei påvist av tidligere graver Trygve Erikssen. Han fortalte og at der låg fleire pomorgraver i utmarka ( ... ) Ifølge Eriksen skal klokka fra Kiberg være havna i Nesseby kirke, og en messehagel i Oscar`s kapell i S. Varanger" (Bratrein 8/8 1968). 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). Avstanden fra nåværende kirkegård til "vestre banehalvdel" er 250-300 m, til skolen ca. 400 m. Åsen øst for Kiberg heter Korshaugen. (Kildegjennomgnag til registreringa av middelalderkirkesteder av NIKU ved Jan Brendalsmo, RA sak 06/02235-81).
Eldre beskrivelse:
Lokaliseringen av kirkestedet er uavklart. - Kirketomta og kirkegården - umulig å stedfeste nøyaktig. I dag er ingenting å se av den gamle kirketomten i Kiberg Ytre. Tyskerne satte opp flere brakker her under 2. verdenskrig. Og i 1966 ble Kiberg nye skole reist på den gamle kirketomten. Kiberg Ytre var kirkested i reformasjonsårhundret og til henimot midten av 1700-tallet. Kirketomten midt inne på kirkegården var ifølge Nicolaisen (1892) henimot 20 m lang, koret iberegnet. Korets bredde ca 6 m. Kirken ble "sløyfet" i 1747. En del av inventaret, bl.a. en alterbok "Kiberg anno 1725", (Nicolaisen) ble ført til Varanger = Nesseby kirke. De to klokkene ble ført til Vardø kirke. Kiberg kirke var til allerede i 1589. I 1667 ble en ny kirke bygd i Bergen og oppsatt i Kiberg. I 1698 var Kiberg kirke den nest rikeste av Finnmarks kirker. Ved gravingen av skoletomten 1965 ble det funnet en hel del skjeletter i jorden. Desuten i Kiberg elven som går i Ø-kanten av kirkegården. De var tatt av flommen. Skjelettene ble kjørt til "lasteplassen" nær Kibergvannet. Vel 2 km fra Kiberg skole, på hovedveien mot Vardø, tar en liten vei av mot Kibergvannet. Ca. 150 m nedover denne veien, på S-siden ligger "lasteplassen", der skjelettene ble tømt. Hit ble også bena fra nest eldste kirkegård fraktet. Det ligger et tynt sandlag over. Kibergs eldste kirkegård lå altså der den nye skolen i Kiberg ligger nå. Vanskelig å si presis hvor kirkegården og kirken lå, derfor sirkles bare skolen og området Ø-over til elven inn på flyfoto. Neste kirkegård ble anlagt ca 100 m V for første. Den ble dels rasert under siste krig (barakken) og dels ved anlegg av idrettsplass. Alt som sees i dag er en gravsten og noen råtne gjerdestolper fra kirkegårdens Ø-side. Lengde ca 70 m, bredde ca 50 m, Orientert N-S. Ca. 400 m V for skolen lå tidligere ca 20 russegraver. Ivar Randio sier at bena ble tatt opp og sendt til fellesgravplassen på Tjøtta etter krigen. Gravene lå på rad i N-enden av den nyeste kirkegården, dvs ca 450 m V for skolen. Gravene er fra verdenskrigen 1940 - 45, og russefanger var gravlagt i dem.