Avaldsnes kongsgård lå ved den viktige samferdselsåren Karmsundet - eller Nordvegen, som var det navnet vikingene brukte. Da kongen hadde tatt kristentroen, var det naturlig å bygge en kirke her, og Snorre forteller at det lå en kirke på kongsgården allerede i 1023. Karmøys eneste steinkirke er sannsynligvis den tredje kirka på samme sted.

Olavskirka på Avaldsnes ble reist omkring år 1250 av kong Håkon IV Håkonson. Kirka ble bygd i ung-gotisk stil med spisse buer. Gråsteinsmurene er mellom 1,2 og 2 meter tjukke. Hjørner og rammer rundt dør- og vindusåpninger er av kleberstein fra området ved Tolgetjønn i Haugesund. Manglende vedlikehold resulterte i at store deler av murene forfalt. I 1830-årene ble murene i kor og skip restaurert. Restene av det gamle tårnet ble fjernet, og steinen ble brukt på de andre murene. I 1862 ble det bygd en takrytter - et lite klokketårn - på mønet mot vest.

 Den 16. oktober 1929 ble Avaldsnes kirke vigslet på nytt. Gjenoppbyggingen av tårnet og restaureringen av resten av kirkeskip og kor ble utført etter planene til arkitekt Moestue.

Fatet i døpefonten er fra 1640, og er den eldste gjenstanden som fortsatt er i bruk. En av lysekronene er gitt av den islandske teologen og historieskriveren Tormod Torfæus på 1600-tallet. De andre er kopier. Torfæus bodde sine siste år på Stangaland i Kopervik, og han ble gravlagt i kirka. Gravsteinen hans ligger framme i koret.

De to lysestakene i korbuen er også kopier av en gave fra Torfæus. De ble satt opp i 1998.

Glassmaleriene i koret er laget av kunstneren Bernhard Greve og satt inn til 700-års-jubileet i 1950.

Både hovedorgelet fra 1981 og kororgelet fra 1982 ble bygd av Marcussen og Søn i Danmark. Hovedorgelet har 26 stemmer, og kororgelet hadde 4 stemmer før det i 1996 ble utvidet med en subbass til 4 ½ stemmer. Dette ble utført av Henrik Brinck Hansen.

Jomfru Marias synål

Like innenfor porten til kirken, kan du til venstre se rester av en bautastein. Det heter seg at steinen, som på 1600 tallet var over 9 m høy, sprakk da prestegården brant i 1698. Denne bautaen er en av disse steinene. En annen er “Jomfru Marias synål” som du kan se på nordsida av kirken.

Med sine 7,2 m er dette en av Norges høyeste bautaer. Steinen skal ha vært enda høyere. Sagnet forteller nemlig at dommedag kommer når steinen berører kirkeveggen. Derfor skal Avaldsnesprestene i ly av nattemørket ha hogget biter av toppen og slik reddet verden fra undergang. Også de som bygde kirken hadde respekt for denne steinen og skrådde av den grunn nordveggen i skipet fra steinen. I dag er avstanden mellom dommedagssteinen og kirkeveggen 9,2 cm.