Den største initiativtakeren til å få bygget en kirke i Olderdalen, var nok skolestyrer Peder Soleng. Med sine gode kontakter rundt om kring, lyktes ham med å få tak i en meget stor brakke som kunne brukes. Arbeidet med kirken kom godt i gang, med bred støtte fra både befolkningen, og soknepresten i Lyngen, Nils Rødberg. Fra starten av var ikke departementet involvert i byggeplanene. Da de fikk høre om hva som foregikk, stilte de seg kritiske til et så stort prosjektet i en liten bygd, rett etter krigen. Svaret ble at kirken bare skulle være helt provisorisk, noe departementet slo seg til ro med.
Arkitekt Kirsten Sand ved Finnmarkskontoret, fikk oppdraget med å lage tegninger av kirken. Det skulle etter hvert vise seg at materialene i den store brakken ikke var nok, men tilfeldigvis var en dampbåt fra Fredrikstad på vei inn fjorden med materialer. Kirken ble bygget ferdig ved hjelp av snekkere fra Ullsfjord, og ble vigslet til bruk søndag 19. juni 1949. Selve vigslingen ble utført av biskop Wollert Krohn Hansen, assistert av fylkesprost for gjenreisningen, Alf Wiik, sokneprest Rødberg m.fl.
Selv om kirken nå var innviet, la ikke kirkeforeningen ned arbeidet av den grunn. Mye av inventaret er kommet på plass i årene etter innvielsen. En god del er kommet i form av gaver fra lokale personer, foreninger og foretak, mens kirkeforeningen har vært pådriver for de større innstalasjonene - som blant annet altertavle og orgel. Se bildegalleri nederst på siden for flere detaljer.
Kirkens første orgel kom på plass i 1953, altså fire år etter innvielsen. Orgelet var bygget av Vestres orgel- og pianofabrikk på Haramsøy, og hadde 5 stemmer. I 2002 ble det gamle orgelet erstattet av et nytt instrument, bygget av Knud Jønsson/Albert Lang. Dette orgelet har 12 stemmer, fordelt på 2 manualer og pedal.
En litt spesiell funksjon som det nye orgelet har, er en egen bryter der man enkelt kan justere hastigheten på tremoloen. Deler av det gamle orgelet (spillepult, samt 8' i man. og 16' i ped.) ble for øvrig brukt til å sette opp et lite, men fult fungerende orgel på Kultursenteret i Olderdalen.
Fram til 1978 var Kåfjord en del av Lyngen prestegjeld, men det har vært hjelpeprester med tjenestested i kommunen siden 1948. Bakerst i kirken finner vi et kjøkken og det som i dag er dåpsrom. Fram til det ble bygget egen prestegård i 1963, bodde presten i denne lille leiligheten. På den tiden ble også sakrestiet mot sørvest brukt som prestekontor.