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 kirken på samme sted.
Olavskirken på Avaldsnes ble reist omkring år 1250 av kong Håkon IV Håkonson. Kirken 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 Mostue som vant arkitektkonkurransen i 1919. Bildet over viser kirken slik den så ut før denne restaureringen ble påbegynt.
Fatet i døpefonten er fra 1640, og er den eldste gjenstanden som fortsatt er i bruk.
Lysekronen i det sør-vestre hjørne av skipet 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 kirken. 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.
Fra gammel tid står en bauta på nordsiden av kirken. Det er "Jomfru Marias synål". Legenden vil ha det til at når bautasteinen treffer kirkeveggen ville det bli dommedag. Bildet viser utsikten fra toppen av bautaen, 7,2 meter over bakken.
Les mer om denne bautasteinen her.