Kirkja í Heydölum var helguð heilögum Stefáni í kaþólskum sið. Tvær kirkjur voru á staðnum.
kirkjan í Heydölum var smíðuð 1856 en hún brann til kaldra kola 17. júní 1982. Með henni brunnu altari, predikunarstóll og tvær fornar klukkur, allt merkilegir hlutir. Kirkjan var afhelguð 13. júlí 1975 og tekin af fornminjaskrá nokkru síðar.
Yngri kirkjan sem er steinsteypt var vígð 13. júlí 1975 og var hún í 18 ár í byggingu með hléum. Altaristaflan er frá 1865, máluð af Fiebig, dönskum málara, og sýnir krossfestinguna. Þekktasti prestur í Heydölum er sér Einar Sigurðsson (1538 – 1627). Eftir hann liggur meira af kveðskap, prentuðum og óprentuðum, en nokkurn annan Íslending. Þekktur er jólasálmur séra Einars sem hefst svona:
Nóttin var sú ágæt ein,
í allri veröld ljósið skein,
það er nú heimsins þrautarmein
að þekkja hann ei sem bæri.
Með vísnasöng eg vögguna þína hræri.
