Mainitaan pitäjänä 1751. Alkuaan seurakunta oli jaettuna Koutokeinon pääpitäjään ja Afjuvarren anneksipitäjään, joka tunnetaan myöhemmin Karasjokena (Karasjok). Seurakunnan pappi vapautettiin Porsanginvuonon (Porsangerfjorden) suomalaisten palvelimesta kuninkaallisella käskykirjeellä 19.7.1793, jonka jälkeen hänen vastuullaan oli vain varsinaiseen seurakuntaan kuuluneiden Karasjoen suomalaisten sielunhoito. Seurakunta yhdistettiin Ryssänmarkan (Kistrand) seurakuntaan kuninkaallisella käskykirjeellä 19.3.1813 ja erotettiin itsenäiseksi kirkkoherrakunnaksi 30.1.1851. Kappelin rakentamiselle Masiin annettiin lupa kuninkaallisella käskykirjeellä 19.7.1927.
Muut nimet
Guovdageaidnu, Kautokeino
Arkisto
Koutokeinon seurakunnan ministeriaalikirjat (ministerialbok) alkavat vuodesta 1723 ja lukkarinkirjat (klokkerbok) eli kirkonkirjojen duplikaatit vuodesta 1862. Ministeriaalikirjat puuttuvat vuosilta 1776–1805 ja vanhempia tietoja löytyy Ryssänmarkan (Kistrand) seurakunnan kirkonkirjoista vuosilta 1805–1843. Seurakunnan arkistoa säilytetään Tromssan valtionarkistossa (Statsarkivet i Tromsø).