Hedenstad kirke er bygd av naturstein og stammer fra tiden mellom 1200 og 1336, da kirkens prest blir nevnt for første gang. Kirken var viet til erkeengelen St. Michael. Det antas at det har stått en stavkirke på samme sted. Hedenstad kirke hadde i 1395 forholdsvis mye jordegods, dette tyder på at det har vært et gammelt kirkested.
I årene 1781 - 82 ble det gjennomført en omfattende restaurering, blant annet stammer det nåværende tårnet fra denne ombyggingen.
Ved en ny restaurering i 1888 ble det gjort en del endringer ledet av arkitekt H.M.Backer fra Oslo:
- Det gamle våpenhuset foran inngangen ble erstattet av en forhall.
- Det ble satt opp to sakristier langs begge langsidene, hver med egen inngang.
- Vinduene på sørsiden ble gjort større.
- Det ble bygd et galleri langs den nordre veggen for å skaffe flere sitteplasser.
- Tårnet fikk bordkledning, spiret ble kledd med jernplater og taket ble dekket med valdresskifer.
- Det ble satt inn ny altertavle og prekestol. Altertavlen er en kopi etter et maleri av den danske maleren Anton L.J.Dorph. Kopien er lagd av Dina Aschehoug i 1889 og viser "Kristus og de to disipler på vei til Emmanus". Den gamle altertavlen fra 1697 henger fortsatt i kirken.
Det nye orgelet ble innviet 4. mai 1981.