Tretten kirke ble innviet 12. september 1728 og fikk navnet «Vår Frelsers Kirke». Den erstattet en tømret langkirke fra 1580-årene som var blitt for liten. Den gamle kirken lå lenger oppe i dalsida, på Kjørkjehaugen. Det finnes samme type sagn for Tretten kirke som for Øyer kirke. Tømmeret ble først kjørt til Moesplassen (der Aurvoll skole senere ble bygd), men av mer eller mindre naturlige årsaker ble tømmeret flyttet til stedet der kirken står i dag.
Da kirken ble tatt i bruk var den verken bordkledt eller malt. Bordkledningen kom i 1747 og i 1774 ble kirken tjærebredd. I 1807 ble den malt for første gang, antakeligvis rød. Den hvite fargen kom først i 1875. Deler av den tømrede langkirken på Kjørkjehaugen antas å være gjenbrukt i sakristiet.
Kirken hadde opprinnelig ikke tårn, bare en tårnfot til klokkene. Selve tårnet ble reist omkring 1807 i forbindelse med annet arbeid på kirken. Tårnet har bydd på stadige problemer helt siden det ble reist. I 2000 ble det konstatert så store skader i bærekonstruksjonen til tårnet at det ble tatt ned og plassert på bakken ved siden av kirken. Nytt tårn, formet som det originale, ble bygget og kirken ble gjenåpnet med det nye tårnet i 2015.
Kirkegården er utvidet i flere omganger. To av gravene er fredet. I den ene graven hviler Johannes og Eli Fossli som ga kapellet til kirka i 1937. I den andre hviler krigsfangen Niklas Sokolow. Tretten kirke har et brurhus, bygd i 1775.