Før denne kirken skal det ifølge sagaen ha vært en trekirke bygget av Olav Tryggvason her. Muligens er det den samme kirken som nevnes meget eksplisitt i Olav den helliges saga. Det er sannsynlig at steinkirken er bygget på samme sted som denne.
Kirken har vært et landemerke for sjøfarere som har reist gjennom Karmsundet de siste 750 årene. Kong Håkon Håkonsson ga tillatelse til å bygge en kirke her rundt 1250. Den var ikke ferdig før 1320, og var den gangen den fjerde største i landet. Kirken ble viet til St. Olav og fikk tittelen Kongelig Kapell av Håkon Magnusson. I den samme perioden ble den én av fire kirker der det ble drevet undervisning, og den hadde en gruppe lærere innen juridiske og teologiske fag. Derfor hadde den også trolig fire prester. Den kan derfor også ha hatt et åttekantet kapittelhus i stein i tilknytning til koret. Dette er nevnt av Peder Claussøn Friis i 1599. Murene skal ha vært synlige så sent som i 1840, men er nå forsvunnet. Kapittelhus er vanlige i de store engelske katedralene.
Avaldsnes var også en av Harald Hårfagres fem kongsgårder på Vestlandet, og ifølge sagaen skal han ha blitt gravlagt i dette området. Rundt kirken finnes gravhauger og bautasteiner, og stedet må ha vært viktig siden romersk jernalder. Like øst for kirken står en seks og en halv meter høy bautastein kalt Jomfru Marias synål. Den lener seg mot kirkemuren, og om den berører muren sier tradisjonen at dommedag er nær. Navnet skal antakelig stamme fra en forsvunnet runeinskrift: Mikael nest Maria. Nest ligner på nesta, som betyr å sy, og folketradisjonen kan dermed ha gitt nevnet på steinen.
Under 2. verdenskrig ønsket tyskerne å rive tårnet, da de mente at det var et landemerke for britiske piloter. Men dette satte riksantikvaren seg i mot og det ble isteden reist et tømmeroverbygg over kirken som kamuflasje.
Den nåværende kirken har en relativt stor grunnflate, men er ikke spesielt høy. Den har et rektangulært skip og et dominerende vesttårn. Skipet sto uten tak i flere hundre år. Dagens tårn er en fri rekonstruksjon av det tårnet som ble revet i 1834. Det har samme grunnflate. Det virker litt for stort til kirken, muligens fordi skipets murer antakelig kan ha vært høyere, og at det opprinnelige tårnet kan ha vært lavere. Store tårn var ellers ikke vanlige på vestlandet, men ellers i Europa hadde ofte kongen sin plass på et galleri i tårnet.
Kirken har lansettvinduer med smale spisse buer. I korets østvegg finnes tre slike ved siden av hverandre. Dette var vanlig i unggotikken og kalles treenighetsvindu.
Spesielt sørportalen har arkitektoniske trekk som setter den inn i det som kalles Bergensgotikken. Andre kirker i denne gruppen er Voss, Aurland, Ullensvang og Kvinnherad.
Ingen av inventardelene fra middelalderen er bevart. Nytt alter, prekestol og benker er tegnet av arkitekt Eyvind Moestue, som foresto kirkens restaurering i 1920-årene.
Bautasteinen «Jomfru Marias synål» ved kirkens nordvegg
Gotisk sørportal på Avaldsnes kirke. Foto: Arne Kvitrud, 2012.
Litteratur
Ekroll, Øystein, Stige, Morten, Havran, Jiri, Middelalder i Stein bind 1 i serien Kirker i Norge, Oslo 2000, ISBN 82-91399-09-3