Mainitaan reformaation aikana 1589, jolloin Vesisaari kuului anneksina Vuoreijan seurakuntaan. Muodostettiin pääpitäjäksi 1694, jolloin Vuoreijasta tuli kappeli, joka erotettiin myöhemmin itsenäiseksi seurakunnaksi 1771. Seurakunta oli jaettuna pitkään kahteen pitäjään, Vesisaareen ja Uuniemeen (Nesseby). Vuoreijasta tuli uudelleen seurakunnan anneksi kuninkaallisella käskykirjeellä 3.12.1819 ja se itsenäistyi uudelleen 7.5.1849. Seurakuntaan kuulunut Uuniemi erotettiin Tenon (Tana) kanssa itsenäiseksi seurakunnaksi 1846 ja Etelä-Varanki (Sør-Varanger) 1864. Uuniemen ja Vesisaaren raja Varanginvuonon molemmin puolin vahvistettiin kuninkaallisella käskykirjeellä 27.2.1863.
Seurakunnan kirkko sijaitsi ensinnä Kirkkosaaressa (Kirkeøen), mutta siirrettiin mantereelle ja vihittiin käyttöön 1711. Tämä kirkko oli käytössä vuoteen 1861 ja se purettiin 1869. Uusi kirkko vihittiin käyttöön Galgebakkenissa 1861. Kuninkaallisella käskykirjeellä 18.3.1857 annettiin lupa rakentaa kirkko Varanginvuonon (Varangerfjorden) eteläpuolelle ja kirkon valmistuttua sitä ympäröinyt alue erotettiin itsenäiseksi Etelä-Varangin seurakunnaksi kuten edellä mainitaan. Lupa kappelin rakentamiselle Annijoelle (Vestre Jakobslev) annettiin 1939.
Muut nimet
Čáhcesuolu, Vadsø, Vadsö
Arkisto
Vesisaaren seurakunnan ministeriaalikirjat (ministerialbok) alkavat vuodesta 1747 ja lukkarinkirjat (klokkerbok) eli kirkonkirjojen duplikaatit vuodesta 1843. Ministeriaalikirjat puuttuvat Vesisaaren kaupungista vuosilta 1839–1873 ja lukkarinkirjat Vesisaaren kaupungista ja maaseurakunnsta 1854–1874. Seurakunnan arkistoa säilytetään Tromssan valtionarkistossa (Statsarkivet i Tromsø). Vesisaaren vihittyjen ja kuolleiden luetteloita löytyy myös Varangin pitäjänkirjurin (Varanger sorenskriverarkiv) arkistosta.