Avaldsnes skal ha fått navnet sitt etter den sagnomsuste kong Augvald, som etter tradisjonen hadde setet sitt i Karmsundet. Her lå et gammelt maktsentrum. Skipsleia presses inn i et trangt sund like ved Avaldsnes, og det er trolig trafikken gjennom sundet som har skapt makt og rikdom gjennom tidene. Harald Hårfagre valgte Avaldsnes til sin viktigste kongsgård omkring år 870, og gjorde det til det eldste kongesetet i Norge.
Etter sagnet lot Olav Tryggvason bygge en kirke på Avaldsnes, trolig som gårdskapell for kongsgården. Det må ha vært en nokså liten stavkirke. Byggingen av dagens kirke, Olavskirken på Avaldsnes, startet omkring 1250 på ordre fra kong Håkon Håkonsson, og sto ikke ferdig før nær 1320. Kirken var viet St. Olav og var en av de største norske steinkirkene fra middelalderen — en av bare fire kongelige kollegiatkirker i landet. Den var en viktig stasjon på pilegrimsleden til Nidaros, som fulgte kysten.
Arkeologi
Det er gjort rike funn fra forhistorisk tid i hele området. Reheia — også kalt Blodheia — ligger omtrent en kilometer vest for kirken. Harald Hårfagre la hovedgården sin til Avaldsnes omkring 870. I 953 kjempet Håkon den gode et hardt slag på Blodheia ved Avaldsnes mot sønnene til halvbroren, Eirik Blodøks. Håkons styrker vant slaget, og han var konge i Norge til han døde i 961.
Stedet rommer det eneste norske eksempelet på bronsealdergravhauger lagt på rekke. En skipsgrav fra merovingertiden (omkring 680–750 e.Kr.) funnet her er i dag den eldste kjente skipsgraven i Norden.
