Kirken på Orrestad er nevnt første gang i 1323, men man vet ikke når den ble bygd. Kirken var en treskipet stavkirke som brant ned i 1722 etter et lynnedslag. Til reisingen av nåværende kirke er det knyttet et par sagn. I følge ett av disse sagnene skulle kirken bygges på Skeid, et par kilometer lenger sør. Tømmeret var lunnet der, men en natt ble tømmeret flyttet til tomten etter den nedbrente stavkirken, og der ble også den nye kirken reist.
Nåværende kirke er en trekirke med korsformet grunnplan som ble reist på forrige kirkes tomt og innviet 1725. Kirken fikk navnet «Den Hellig Treenighets Tempel». Da kirken ble innviet i 1725 hadde den verken bordkledning eller tårn. Tårn og spir ble reist en gang mellom 1748 og 1775. Kirken hadde antakeligvis skifertak og var tjærebredd. Siden har den flere ganger vært malt rødbrun. Det er mulig at den nåværende hvite fargen først kom i forbindelse med et større restaureringsarbeid i 1875. Klokkene hang i en støpul øst på kirkevangen helt fram til 1866, da de ble flyttet opp i tårnet. Etterpå ble både klokkestøpulen og brurhusene fjernet og solgt.
Stallen på kirkevangen ble revet p.g.a. veiutbygging. Kirkegården er utvidet i flere omganger. På kirkevangen står det to bautasteiner. Den eldste av disse ble reist i 1914 og er til minne om øyværinger som «låg ute å verja lanne» i 1807-1814. Den andre ble reist i 1959 til minne om bygdefolk som deltok i krigen 1940-1945.