Kjelvik kirke var i 1589 hovedkirke med annekskirker i Opnan og Helnes. Senere ble Skarsvåg, Måsøy og Sværholt annekser. Opnan kirke nevnes ikke etter 1601 og kirken på Helnes var borte før 1694. Skarsvåg kirke stod i Lille eller Ytre Skarsvåg. Den ble solgt i 1748. Til Kjelvik hørte Kistrand kapell. Sværholt ble ble ved reskript av 2. oktober 1720 lagt til Kjøllefjord prestegjeld. I 1793 ble Kistrand hovedsokn og Kjelvik anneks. Ved kgl.res. 18. mars 1861 ble Kjelvik anneks skilt ut fra Kistrand prestegjeld og lagt til Måsøy prestegjeld. Ifølge kgl.res. 9. juli 1831 ble Kjelvik kirke revet og i stedet ble det satt opp et kapell av materialene. I 1844 ble det oppført ny kirke. Den blåste ned i 1882. Det ble da bygd ny kirke i Søndre Honningsvåg. Den ble innviet i 1885. Kjelvik ble utskilt som eget prestegjeld ved kgl.res. 16. juni 1911. I 1954 skiftet prestegjeldet navn fra Kjelvik til Nordkapp.