Fanø har uden tvivl været beboet før kristendommen kom til Danmark, hvorfor kirkebyggeriet har fulgt samme udvikling, som man har set i resten af Jylland.

Den første kirke på Fanø lå på en plads, der oprindelig blev kaldt Hovens Dal. Navnet betyder, at der i denne dal har ligget et såkaldt gudehov. Et gudehov var en bygning, et helligsted, som man i hedensk tid brugte til at tilbede de gamle nordiske guder, Aserne.

Da kristendommen for alvor kom til Danmark omkr. 960-980 har man nedlagt gudehovet og formentlig bygget en trækirke på dens plads.

En overlevering fra gammel tid fortæller da også at Fanøs første kirke var lavet af jord og drivtømmer. I øvrigt var alle Danmarks tidligste kirker lavet af træ: De der lå inde i landet var bygget af træ der var fældet i skovene, og de der lå tæt ved havet var overvejende bygget af drivtømmer.

Kirken lå i et område der blev kaldt korsdalen. Navnet virker indlysende, eftersom korset er kristendommens stærkeste symbol, og man har villet understrege bekendelsen til den nye religion ved at ændre navn fra det hedenske Hovens Dal til Korsets Dal. Det er måske endda korsbrødre-ordenen i Ribe, der har udvist initiativ til at der blev bygget kirke på Fanø, og at man som tak har opkaldt stedet efter denne orden.

Dog har Leif Norking en teori der nok er mere sandsynlig: Stednavne der indeholdt ordet ”kors” angav indsejlingen til en markedsplads ved en naturhavn, som af den lokale magthaver var beskyttet mod overfald og plyndring.
Et generalstabskort fra 1872-73, hvor både navnene Østerkors og Vesterkors er anført underbygger denne teori, da der jo ikke har været to kirker.

I 11 hundredetallet blev trækirken erstattet af en stenkirke. Den må have haft en portal med hugne granitsøjler, for der findes rester af en sådan to steder på Fanø. 
Ved gården som ligger på hjørnet af Niels Sørensensvej og Vestervejen i Nordby findes en smuk søjlebase som antagelig er hugget i 11 hundredetallet af en stenhugger, som har arbejdet på Ribe domkirke. Stenen befinder sig kun godt 100 meter fra Nordby kirkes bagside, og må være blevet slæbt med da kirken i Rindby blev revet ned.

Også i Sønderho kirke findes antageligt en rest af granitsøjlen. Døbefonten står på et omvendt romansk kapitæl der sandsynligvis stammer fra samme tid og sted.

Endelig siges det at det stadig er muligt at finde munkesten i området, hvor den gamle kirke i Albo har stået.

Kirken har sandsynligvis været bygget af danske munkesten og rhinske tufsten. Tuf er en porøs vulkansk stenart som var meget udbredt til stenbygninger på denne tid. I det syd- og sønderjyske er over 50 kirker helt eller delvist bygget af tuf, bl.a. Ribe Domkirke.

Grunden til at man valgte at bruge tuf var, at man ikke havde særlig store mængder natursten i området, hvorfor man valgte at importere dette materiale som blev fragtet til kysten langs Vadehavet fra egnene omkring Rhinen i Tyskland og Holland.

Om det var den kirke der blev indviet til Sankt Anna, hvorfor dalen skiftede navn og kom til at hedde St. Anna Dal, eller om også den første kirke var indviet til denne helgen vides ikke med sikkerhed, men da den hellige Anna ikke spiller nogen betydelig rolle i folkefromheden i Danmark før hen imod 1400-tallet, må vi antage at det kun var stenkirken, der blev opkaldt efter Sct. Anna – og det måske endda flere hundrede år efter at kirken blev bygget.

I 1400 tallet må beboerne allerede have haft store problemer med sandfygning, og det er ikke utænkeligt, at de håbede på bedre levevilkår, hvis de stod under den hellige Annas beskyttelse.

Kirken lå altså i det område der nu er kendt som Annes Dal, umiddelbart vest for Albue Fuglekøje og indtil statsplantagen blev anlagt i 1890’erne stod der stadig diger, der indrammede pladsen.

Anna var før reformationen en vigtig helgen i Norden. Hun var den beskyttende værnehelgen for en rækker grupper, og dertil blev hun og hendes mand Joachim af flere ordenssamfund fremhævet som et forbillede for ægtepar. Ligeledes blev Anna også billedet på den perfekte mormor – for hun var mormor til Jesus.

Sankt Anna var nemlig ifølge traditionen Jomfru Marias moder. I kristen tradition har hun dermed en særlig rolle, som Marias opdrager og som mormor til Jesus Kristus. Dette er særligt betydningsfuldt i de kirkesamfund, som praktiserer helgendyrkelse. Hverken Anna eller hendes mand Joachim er nævnt i Det nye testamente. Den ældste omtale er i Jakobs Forevangelium fra det 2. århundrede, men der er ingen grund til at fæste lid til dette som en historisk korrekt fremstilling. I mangel på oplysninger om dem kaldes de Anna og Joachim.

Hun er ofte kendt under tilnavnet Anna selvtredje, som refererer til den kendteste fremstilling af hende i kunsten: Siddende med Jomfru Maria på skødet, der igen har Jesusbarnet som i sit skød. Sankt Anna

Et gammelt sagn fortæller, at der engang har ligget et fiskersamfund ved det nuværende Albue Fuglekøje der hed Østerho. Der findes ingen arkæologiske fund der understøtter denne påstand, for der er endnu ikke foretaget udgravninger i området, men man har altid bygget kirker hvor befolkningskoncentrationen var størst, så sagnet taler sikkert sandt.
Østerho betyder ”det østlige fremspring” ligesom Sønderho tilsvarende betyder ”det sydlige fremspring” og da kirken har ligget umiddelbart nord for Annes Dals bjerge, der så afgjort er et fremspring, så er det lige før at sagnet kan – om end ikke bekræftes så dog sandsynliggøres.
I langt de fleste kilder kaldes bebyggelsen dog ikke Østerho, men Albo, som må være en forvanskning af Albue.

Det er meget naturligt, at det netop var ved Albue, den første bosættelse fandt sted. Området rakte langt længere mod øst end det gør i dag, og samtidig rakte Jylland længere mod vest. Der var altså kun ganske kort afstand fra fastlandet til Fanøs østlige fremspring. Desuden var der en fin naturhavn.

Johannes Mejers kort fra 1649, hvor det ses at Fanø og Jylland lå tættere på hinanden end i dag.

Da Albo blev beboet, var afstanden endnu mindre.

Kirken optræder i ”Ribes Oldemor’s ” kirkefortegnelse fra omkr. 1340, hvor den svarer 2 sterling i afgift til Domkapitlet i Ribe. Det er det første skriftlige bevis på kirkens eksistens.

Godt og vel 300 år gammel blev kirken før den var i så elendig forfatning at den måtte brydes ned.

Den sandflugt der nok bar størstedelen af skylden for kirkens forfatning har selvfølgelig også gjort det vanskeligt at bo og dyrke jorden i området.

Desuden blev Fanø ramt af en voldsom vandflod d. 2. november 1532, der måske kan have fremskyndet planerne om at flytte kirken.

Befolkningen flyttede derfor mod henholdsvis nord og syd, hvor der må have været bedre livsbetingelser i 1500-tallet. Derved opstod også behovet for to kirker.

Udflytningen er selvfølgelig sket gradvist over flere generationer, og der har boet mennesker i nærheden af den nuværende kirke i Sønderho og den tidligere kirke i Rindby længe før kirken i St. Anna Dal blev nedbrudt, ligesom der nok har boet mennesker i området Albo en rum tid efter de mistede deres kirke.

Blandt andet ved man fra Riberhus Lensregnskab fra 1538, at der var beskatning af 21 skibe i Sønderho sogn, hvoraf de 10 var hjemhørende i Albo, altså i den gamle bosættelse ved Albue Bugt. 17 skibe blev beskattet i Nordby, altså i Fanø sogn.

Albo – og dermed de første kirker – lå altså i det område der ved udflytningen blev til Sønderho sogn. I 1500-tallet var den ø vi i dag kender som Fanø delt af et sund, hvorved der reelt var tale om to øer. Den nordlige ø hed Fanø og den sydlige hed Sønderho, og de første kirker i Sct. Annas dal lå syd for sundet.

Det ses stadig på Fanøs sognekort, at sognegrænsen slår et sving om kirken ved Albo. Egentlig rækker Nordby sogn længere sydpå end Sct. Annas Dal, men man har valgt at slå en bue udenom, da dalen ligger syd for Elses Gab, og derfor geografisk ligger i Sønderho sogn.

Den nordlige kirke kom til at ligge i Rindby. Man kender ikke den nøjagtige placering, men det var på den matrikel, hvor Rindby kirkegård og det gamle kapel nu ligger. Det var den kirke der blev bygget først. I en bevaret liste fra Riberhus lensregnskaber fra 1538 er Sønderho nemlig ikke betegnet som kirkeby, i modsætning til Rindby.

Desuden er det nærliggende at tro, at man har ladet Sct. Annas kirke følge Sønderho da øen blev delt i to sogne, idet beboerne på den nordlige del af øen allerede var i gang med at bygge i Rindby, jfr. sognekortet ovenfor.

Da den sydlige kirke blev bygget 5-10 år senere, blev den placeret i den vestlige del af byen Sønderho ved øens sydspids, på præcis samme sted som hvor den nuværende Sønderho kirke ligger.

Man ved ikke præcist hvornår St. Anna kirke blev nedbrudt, men dens første afløser blev bygget i Rindby på et tidspunkt mellem 1524 og 1537 – måske efter den store vandflod i 1532 - og kirken i syd blev bygget i Sønderho mellem 1538 og 1945. Sct. Anna er nævnt i lensregnskaberne fra 1538, hvor den betegnes som ”Kircheby”, så mon ikke den blev brudt ned umiddelbar før Sønderho kirkes opførelse så man kunne genbruge materialerne?

Når man kan afgrænse dateringen så præcist skyldes det at man ved, at der ingen kirker blev bygget i Ribe stift mellem 1340 og 1524. I 1538 nævnes Rindby som kirkeby, mens Sønderho ikke står anført som havende en kirke. 
I 1545 nævnes Sønderho kirke første gang i en konge­lig befaling om afgivelse af lod til kirkernes forbedring.

Man har ikke fået alle stenene med sig, da man brød kirken i Albo ned, for lokale, der levede i starten af 1900-tallet, har berettet at de har fundet stenbrokker på stedet, hvor kirken har stået, og i samme periode skal plantør Brühl have fundet grundmuren, opført af munkesten (Peder Andersen Pedersen: ”Nordby sogn, Fanø).

Om opsplitningen til 2 sogne skrev præsten i Sønderho følgende i 1776: Siden er den (S. Annæ kirke) formelst sandflugt blevet fordærvet, nedbrudt og flyttet og beboerne delte i tvende menighe­der, da Nørby sogn flyttede kirken til nør, og Sønderho sogn sin kirke til sønder.” (Kilde: Kirkerne på Fanø, p. 2108).