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 palvelemisesta kuninkaallisella käskykirjeellä 19.7.1793, jonka jälkeen papin vastuulla oli ainoastaan 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 vuosilta 1805–1843 tietoja löytyy Ryssänmarkan (Kistrand) seurakunnan kirkonkirjoista. Seurakunnan arkistoa säilytetään Tromssan valtionarkistossa (Statsarkivet i Tromsø).