Kring 1190 veit vi at kyrkja vart lagd under Kristkyrkja i Bergen, og i 1308 finn vi Herdla som eitt av dei 14 kongelege kapella underordna hovudkapellet, Apostelkyrkja i Bergen.
Herdlakyrkja var ei steinkyrkje i ein enkel romansk stil, men ho vart seinare bygd om i gotisk stil med spissbogar. Frå 1727 var kyrkja i privat eige fram til 1859, då ho vart kjøpt av Herdla sokn. Etter ein stormskade vart kyrkja riven i 1861, og ei større kyrkje vart reist på dei same tuftene i 1863. Denne gjekk opp i flammar i 1934, og etter gjenreisinga vart kyrkja kalla «Øygardskatedralen».
Under krigen fekk bygningen store skadar. Tyskarane sprengde tårnet og nytta skipet til ammunisjonslager. Under golvet vart det grave nedgang til eit vidt forgreina tunnellanlegg under gravplassen. Etter krigen vart kyrkja gjenreist, og ho vart innvigd av biskop Ragnvald Indrebø i 1951.