Alkuaan Ruotsin Härnösandin hiippakunnan Kautokeinon emäseurakunnan anneksi. Mainitaan ensimmäisen kerran kylänä 1551. Koutokeino jäi vuoden 1747 rajakäynnissä Norjan kuningaskunnan puolelle ja Utsjoki Ruotsin, minkä jälkeen Utsjoen kappeli määrättiin yhdessä Kuusamon emäseurakunnan Inarin kappelin kanssa muodostettavaksi omaksi kirkkoherrakunnaksi kuninkaallisella kirjeellä 26.6.1747 ja seurakunta määrättiin kuuluvaksi Turun hiippakuntaan. Aluksi kirkkoherra määrättiin asumaan Utsjoella talvisin, jolloin saamelaiset peuroineen oleskeli täällä, mutta heidän siirtyessä kesäisin merenrannalle, piti kirkkoherran muuttaa Inariin, jonka asukkailla oli vakinaiset asunnot. Myöhemmin kirkkoherra oleskelivat kesäisin pitäjän eteläosissa ja muuttivat vasta talven alussa Utsjoelle. Lapin kirkollisten asian johtokunta määräsi kirjeessä 9.11.1748, että saamen kieltä tuli käyttää katekeettakouluissa ja jumalanpalveluksissa. Saameksi saarnattiin etenkin juhlina ja silloin, kun ihmisiä oli enemmän koossa, jos pappi siihen kykeni, ja tavallisesti saarnattiin suomeksi. Seurakuntaan kuulunut Inarin kappeli erotettiin itsenäiseksi kirkkoherrakunnaksi 1881. Utsjoen kunta perustettiin 1876.
Alkuaan seurakunnassa oli kaksi kiertävää katekeettaa ja kolmas virka asetettiin keisarillisella käskykirjeellä 26.5.1837, mutta käskykirjeellä 20.2.1857 asetettiin näiden sijaan vain yksi katekeetta, jonka tehtäväksi määrättiin opettaminen vakinaisessa koulussa Inarin kirkon luona. Katekeetalta vaadittiin inarinsaamen tuntemista, ja keisarillisessa käskykirjeessä 20.2.1858 määrättiin, että katekeetan oli oltava vihitty papiksi tai ylioppilas, jotta hänellä oli oikeus lukea hyväksi kaksinkertaiset virkavuodet. Katekeetan palkka oli 150 ruplaa ja sitä korotettiin 100 markalla keisarillisella käskykirjeellä 16.12.1887.
Ensimmäisen Tenojoen varrella Talvadisissa sijainneen kirkon kerrotaan vihavenäläisten polttaneen jo ikivanhana aikana. Sai ensimmäisen varsinaisen kirkon Mantojärven rannalle 1700 ja kirkko tunnettiin nimellä Pyhä Ulrika. Uusi kirkko määrättiin rakennettavaksi kivestä keisarin käskykirjeellä 30.4.1842 ja rakentamisen kustannuksiksi arvioitiin 6 841 ruplaa. Seurakuntaan on kuulunut myös Outakosken rukoushuone eli kinkeritupa vuodesta 1853, jossa aikanaan pidettiin lukukinkereitä kesäisin. Outakosken lisäksi kulmasaarnoja pidettiin kinkerien aikaan Nuorgamissa.
Muut nimet
Ohcejohka, Aritsby
Kylät
Kirkonkylä, Nuorgam (Njuorggán), Outakoski (Vuovdaguoika)
Naapuriseurakunnat
Inari, Kaarasjoki, Teno, Uuniemi
Papisto
Kirkkoherrat
1747–1757 Anders Hellander
1758–1765 Henrik Wegelius
1766–1781 David Eric Högman
1782–1793 Henrik Sund
1794–1797 Samuel Castrén
1798–1804 Johan Wegelius
1804–1816 Henric Wegelius
1820–1833 Jakob Fellman
1833–1846 Karl Fredrik Stenbäck
1848–1852 Fredrik Vilhelm Stjerncreutz
1854–1859 Anders Andelin
1860–1866 Edvard Vilhelm Borg
1868–1871 Evert Brynolf von Konow
1877–1886 Jonatan Gummerus
1887–1892 Viktor Alfred Virkkula
1893–1899 Aukusti Koivisto
1900–1905 Aukusti Hakkarainen
1906– Pekka Rudolf Heikinheimo (Heikel)
Ylimääräiset papit
1798–1799 Erik Castrén, vt. kirkkoherra
1819 Jakob Fellman, sijaiskirkkoherra
1831–1833 Karl Fredrik Stenbäck, kirkkoherran sijainen
1845–1848 Fredrik Vilhelm Stjerncreutz, sijaiskirkkoherra
1883–1885 Viktor Alfred Virkkula, vt. kirkkoherra
1886–1887 Viktor Alfred Virkkula, vt. kirkkoherra
1892–1893 Aukusti Koivisto, vt. kirkkoherra
1904 Lauri Arvid Itkonen, vt. kirkkoherra
1905–1906 Lauri Arvid Itkonen, vt. kirkkoherra
Arkisto
Utsjoen seurakunnan rippikirjat alkavat vuodesta 1742, tilikirjat vuodesta 1721 ja historiakirjat vuodesta 1742. Haudattujen luettelot puuttuvat vuosilta 1821–1840. Seurakunnan pappila paloi 10.4.1834 ja edelleen käytännössä olevan ehtoolliskalkin jalassa on kirjoitus: "Efter eldsvådan på Utsjoki prestegård den 10 Aprill 1834 omgjord på Eccl. Fondens bekostnad 1840". Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1696–1987.