Eldste omtale av en kirke på (gnr. 80) Tjeldsund (Hol) er i 1589 (Hols korszhusz, Thr.R. 86). Kirken står ute på Kjerkneset 3-400 m sørøst for tunet på Hol. Muligens ble det reist ny kirke på stedet i 1703 - eller den eldre kirke var blitt renovert. Uansett ble det i 1768 innviet en langkirke med sakristi og der koret hadde samme bredde som skipet, men uten korsarmer eller tårn; våpenhuset var reist i materialer fra den revne kirken. Samlet lengde var ca. 16 m, bredde ca. 5 m. Denne kirken skal ha stått nærmere sjøen enn nåværende kirke, på ei tomt inntil det som nå er kirkegård: ¿Ifølge rapporten fra Riksantikvarens utsending fra slutten av 1940-tallet plasseres denne i østenden av den senere kirkegården¿. Dvs. på den eldste delen av nåværende kirkegård. Nybygget ble stående til 1862, da det etter riving ble solgt til en privatperson som bygde fjøs og stabbur av materialene. I 1899-1901 ble den nye kirken demontert og deretter kraftig ombygd etter at grunnmurene var blitt utvidet. Kirken framstår i dag som en langkirke i tømmer med rektangulært skip og smalere, rektangulært kor med smalere, apsidal avslutning. På hver side av koret er det sakristier. I vest er et våpenhus med tårn, og to små utbygg/fløyer på hver side av skipet gir grunnplanen et preg av korsform. Kirkegården er i flere omganger blitt utvidet mot nord, vest og nordøst (Nielssen 1990:376f, Steinsvik 2001:13ff). En periode i etterreformatorisk tid ble kirke kalt Stoche korshuus (1720), deretter igjen (fra 1735) Hol kirke, visstnok som følge av endringer i eiendomsgrensene mellom nabogårdene Hol og (79) Stokke (Steinsvik 2001:13f). I 1589 lå Hol som anneks til Lødingen hovedkirke og ble btjent hver tredje helligdag av hovedpresten (Thr.R. 86). Inne på kirkegården i vest finnes en markering på ØK med rune-R, en gravhaug.