Tidlegare kyrkjer
Kyrkja i Hyllestad er først nemnd i ei skriftleg kjelde frå 1322. Dette var mest truleg same kyrkjestad som var i bruk til 1880. Den første omtalen av kyrkja på Hyllestad skriv seg frå 1691. Den tømra bygningen hadde då eit kyrkjeskip på 12 x 9 meter, medan koret var 4,5 meter langt og vel 6 meter breitt. Kyrkja hadde våpenhus med tårn. I 1720 vart det bygt nytt tårnspir. Kyrkja var tjørebreidd utvendig og umåla innvendig.
Noverande kyrkje
Plassen på den gamle kyrkjetufta og kyrkjegarden var for liten då ny kyrkje skulle reisast i 1880. Det nye kyrkjestaden vart på Myklebust, ein dryg halv kilometer i sørvestleg retning. Hyllestad-kyrkja er ei langkyrkje i tre. Bygget vart teikna av arkitekt Haakon Nissen, og bygd av John Alver. Dei 300 sitjeplassane gjev plass til godt og vel halvparten av statskyrkjemedlemene i soknet. Bygningsmessig har ikkje kyrkja vorte endra sidan 1880, men fargen er no kvit, medan kyrkja var gulmåla som ny.
Inventar
Gamlekyrkja med inventar vart seld på auksjon i 1881. Døypefonten vart seld til ein gardbrukar på Akse, som nytta han til vask i nesten femti år. Då kom han på plass i den nye kyrkja.
Døypefonten er av kleberstein, og skriv seg frå mellomalderen. Døypefatet er kring 300 år gammalt. Altarlysestakane er òg frå mellomalderen, medan altartavla er av nyare dato, laga i 1902 av Maren Sverdrup. Preikestolen er frå 1880. Kyrkja kan og skilte med ei katekismetavle frå 1600-talet.
Sokn og kyrkjegard
Hyllestad sokn høyrde til Askvoll prestegjeld fram til 1861. Då vart Hyllestad eigen kommune og eige prestegjeld. Det sentrale møtepunktet i den nye kommunen vart då garden Hyllestad. Der låg òg kyrkja på den tida.
Etter 1880 den nye kyrkjegarden på Myklebust den sentrale samlingsstaden. Tett ved kyrkja kom i 1970-åra ungdomsskule, kommunehus, bank, post, butikk og byggefelt, alt saman typiske ingrediensar i det moderne utkantsentret. Det var prestegarden, med lett tilgjengeleg byggegrunn sentralt plassert både i soknet og kommunen, som var utgangspunktet for kommunesentret, ikkje kyrkja i og for seg. Kyrkjegarden vart utvida i 1975.