Alkuaan Ruotsin Härnösandin hiippakunnan Kautokeinon emäseurakunnan anneksi. Utsjoki 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, jolloin seurakunta määrättiin kuuluvaksi Turun hiippakuntaan. Aluksi kirkkoherra määrättiin asumaan Utsjoella talvisin, jolloin saamelaiset peuroineen oleskelivat siellä, mutta heidän siirtyessään kesäisin merenrannalle, piti kirkkoherran muuttaa Inariin, jonka asukkailla oli vakinaiset asunnot. Myöhemmin kirkkoherrat oleskelivat kesäisin pitäjän eteläosissa ja muuttivat vasta talven alussa Utsjoelle. Lapin kirkollisten asiain johtokunta määräsi kirjeessään 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. Utsjoen kunta perustettiin 1876.
Ensimmäisen Tenojoen varrella Talvadisissa sijainneen kirkon kerrotaan vihavenäläisten polttaneen jo ikivanhana aikana. Seurakunta sai ensimmäisen varsinaisen kirkon Mantojärven rannalle 1700 ja kirkko oli Pyhä Ulrikan nimikko. Uusi kirkko määrättiin rakennettavaksi kivestä keisarin käskykirjeellä 30.4.1842 ja sen rakennuskustannuksiksi arvioitiin yhteensä 6 841 ruplaa. Kirkko rakennettiin Utsjoen kirkonkylän eteläpuolelle saksalaissyntyisen arkkitehti Ernst Lohrmnannin suunnitelmien mukaan 1850–1853.
Seurakuntaan kuulunut Inari erotettiin itsenäiseksi kirkkoherrakunnaksi 1881. Seurakuntaan on vuodesta 1853 kuulunut myös Outakosken rukoushuone eli kinkeritupa, jossa aikanaan pidettiin kesäisin lukukinkereitä. Outakosken lisäksi kulmasaarnoja pidettiin kinkerien aikaan Nuorgamissa.
Muut nimet
Ohcejohka, Aritsby
Kylät
Kirkonkylä, Nuorgam (Njuorggán), Outakoski (Vuovdaguoika)
Naapuriseurakunnat
Papisto
Hornborgin ja Wennerströmin Suomen seurakuntien ja papiston matrikkelin (1885) mukaan kirkkoherran virkatalo oli väliaikaisesti virkataloksi määrätty 1856 ja sijaitsi kolmasosa virstan päässä kirkossa Mantojärven rannalla. Virkatalo oli hyvin rakennettu. Päärakennuksessa oli seitsemän suurta huonetta, kyökki ja tampuuri, jonka lisäksi oli pienempi asuinrakennus, jossa oli neljä huonetta ja kyökki. Ulkohuoneet olivat hyvät. Virkatalolla oli peltoa yksi tynnyrinala, niittyä 12 tynnyrinalaa ja metsää, joka oli jakamaton, huonoa ja kasvoi vaivaiskoivuja. Jäkälän avulla riittivät heinät yhdelle vetohärälle ja viidelle lehmälle.
Kirkkoherran palkka oli edellä mainitun matrikkelin mukaan 1880-luvulla valtiota 3 500 markkaa, joka maksettiin Oulun läänin rahastosta. Kahden viikon virantoimituksesta Kivijärven rukoushuoneessa joka toinen vuosi kirkkoherra sai 200 markkaa. Saamen kielen taidosta maksettiin 600 markkaa. Seurakuntalaiset maksoivat kirkkoherralle lihaa tai kalaa kaikilta verovelvollisilta yhden leiviskän eli 4 markkaa, jokaiselta ripillä käyvältä yhden oravannahkan eli 25 penniä, maahanlaskusta isännän tai emännän jälkeen naarasporon, lapsista ja muista puolileiviskää haukia eli 2 markkaa 50 pernniä tai paria kaksi paria rukkasia eli 3 markkaa 50 penniä, joka kolmanneltakymmenenneltä porolta yhden naulan juustoa eli 1 markka 15 penniä sekä kuulutuksista, vihkimisistä, ristimisistä ja kirkkoonotosta eli kirkottamisesta puolileiviskää haukia tai kaksi paria rukkasia tai 12 oravannahkaa eli 3 markka 50 penniä. Seurakuntalaisilla oli velvollisuus tuoda vuosittain kirkkoherralle ruokavaroja 30 porokuormaa Norjasta. Kirkkoherran palkka oli yhteensä noin 5 450 markkaa. Lukkarin palkka oli 125 markka sekä tavan mukaan vihkimiseltä 1 markka, joiden lisäksi seurakuntalaiset maksoivat hautauksilta varojensa mukaan.
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.
Kirkkoherran virkatalon korjaustöitä varten myönnettiin 2 812 markkaa Lapin kirkollisesta rahastosta keisarillisen senaatin päätöksellä 5.2.1901. Kruununmaan luontoisen maa-alueen yhdistämisestä Utsjoen hautausmaahan keisairllisen senaatin pätös 23.11.1903.
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
1892–1898 Aukusti Koivisto
1900–1905 Aukusti Hakkarainen
1906–1915 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 Aukusti Koivisto, vt. kirkkoherra
1898–1899 Aukusti Koivisto, vt. kirkkoherra, Kittilän kirkkoherra
1899 Lauri Arvid Itkonen, vt. kirkkoherra, Inarin kirkkoherra
1904 Lauri Arvid Itkonen, vt. kirkkoherra, Inarin kirkkoherra
1905 Lauri Arvid Itkonen, vt. kirkkoherra, Inarin kirkkoherra
1909 Lauri Arvid Itkonen, vt. kirkkoherra, Inarin kirkkoherra
1912 Lauri Arvid Itkonen, vt. kirkkoherra, Inarin kirkkoherra
Arkisto
Utsjoen seurakunnan rippikirjat alkavat vuodesta 1742, tilikirjat vuodesta 1721 ja historiakirjat vuodesta 1742. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1696–1987.
Seurakunnan 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".
Kansallisarkisto on digitoinut Utsjoen seurakunnan vanhimmat kirkonkirjat noin 1880-luvulle saakka ja aineisto on vapaasti tutkittavissa Astia-palvelussa. Suomen Sukuhistoriallinen yhdistys (SSHY) on digitoinut seurakunnan nuorempia kirkonkirjoja. Alle 125 vuotta vanhojen aineistojen tutkiminen vaatii kirjautumisen yhdistyksen jäsensivuille.