Mainitaan saaneen kirkon jo 1307. Seurakunta mainitaan erillisenä seurakuntana Kiiperin (Kiberg) ja Veisaaren (Vadsø) seurakuntien kanssa uskonpuhdistuksen aikana 1589. Seurakuntaan liitettiin anneksina Makur (Makkaur) 1685. Kirkkoherra asui Vuoreijassa vuoteen 1694, jolloin Vesisaaren kirkosta tuli pääkirkko. Vesisaaren alainen kappalainen asui Vuoreijassa vuoteen 1770, jolloin siitä muodostettiin itsenäinen seurakunta. Muodostettiin uudelleen Vesisaaren alaiseksi anneksiseurakunnaksi kuninkaallisella käskykirjeellä 3.12.1819 ja erotettiin uudelleen itsenäiseksi seurakunnaksi 7.5.1849.
Muut nimet
Vardø, Vardö, Várggát, Vuorea
Arkisto
Vuoreijan seurakunnan ministeriaalikirjat (ministerialbok) alkavat vuodesta 1769 ja lukkarinkirjat (klokkerbok) eli kirkonkirjojen duplikaatit vuodesta 1844. Vanhempia tietoja löytyy Veisaaren (Vadsø) seurakunnan kirkonkirjoista vuotta 1769 edeltävät ajalta. Seurakunnan arkistoa säilytetään Tromssan valtionarkistossa (Statsarkivet i Tromsø).