Nesseby var anneks under Vadsø, men ble ved kgl.res. 31. januar 1846 eget prestegjeld. Tana, som hadde ligget under Lebesby, ble annekssokn i det nye prestegjeldet. I 1861 ble Tana imidlertid skilt ut igjen og ble eget prestegjeld - med unntak av Polmak-distriktet som ble værende under Nesseby. Varanger kirke ble oppført på Angsnes i 1719 i henhold til reskript av 5. september 1718. Den kalles senere Angsnes kapell og ble revet i 1846. Året etter ble kapellet gjenoppført på Nesseby. Nesseby kirke ble bygget i 1858 (kgl.res. 27. juni 1856). Kgl.res. 7. august 1847 gav tillatelse til å bygge Polmak kapell. Grensa mellom Nesseby og Vadsø på begge sider av Varangerfjorden ble fastsatt ved kgl.res. 27. februar 1864. 1. april 1991 ble Nesseby utskilt fra Varanger prosti og overført til det nyopprettede Indre Finnmark prosti. Fra 1.1.1964 ble Polmak kommune slått sammen med Tana kommune (kgl.res. 29. mars 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.