Tanaområdet lå som annekssokn under Lebesby prestegjeld før det ved kgl.res. 31.1.1846 ble lagt under Nesseby prestegjeld. Ved kgl.res. 16.11.1861 ble Tana eget prestegjeld med Tana som hovedsokn. Distriktet Polmak fulgte imidlertid ikke med. En del av Kjøllefjord annekssokn i Lebesby prestegjeld ble lagt til Tana prestegjeld og kalt Gamvik annekssokn. 1.1.1914 ble grensa mellom Tana og Gamvik sokn endret slik at en del av Tana sokn ble overført til Gamvik. Samtidig ble en annen del av Tana sokn skilt ut som eget sokn under navnet Berlevåg annekssokn. Ved kgl.res. 11.10.1968 ble Gamvik sokn utskilt som eget prestegjeld. 1.1.1982 ble Berlevåg skilt ut som eget prestegjeld (kgl.res. 18.9.1981). 1.4.1991 ble Tana utskilt fra Varanger prosti og overført til det nyopprettede Indre Finnmark prosti. 23.12.1940 vedtok Kirkedepartementet å opprette en hjelpepreststilling i Tana. Ved kgl.res. 30.5.1952 ble det i stedet for hjelpepreststillingen opprettet et kallskapellani i Tana. Og ved kronprinsregentens res. 28.6.1957 ble det endret til residerende kapellani. Hjelpepresten/kapellanen bodde i Berlevåg og ser ut til å ha hatt hovedansvaret for dette soknet. Han førte særskilte kirkebøker og dagsregistre og hadde eget kontorhold. Det ble altså skapt et arkiv som var atskilt fra embetets øvrige arkiv. Fra 1.1.1964 ble Polmak kommune slått sammen med Tana kommune (kgl.res. 29.3.1963). I geistlig forstand fortsatte imidlertid Polmak sokn å tilhøre Nesseby prestegjeld. Etter Kirke-, Utdannings- og forskningsdepartementets vedtak - meddelt i brev av 8.4.1998 til Nord-Hålogaland bispedømmeråd - ble Nesseby prestegjeld (soknene Nesseby og Polmak) innlemmet i Tana prestegjeld. Sammenslåingen ble av bispedømmerådet bestemt til å gjelde fra 1.1.1999.