Erotettiin Paltamon pitäjän pohjoisosasta itsenäiseksi kirkkoherrakunnaksi kuninkaallisella käskykirjeellä 23.1.1786. Seurakunnan kirkkoherralle saatiin kuninkaallinen valtakirja, jonka jälkeen seurakunta julistettiin kuninkaalliseksi 19.11.1804. Perustamisen yhteydessä seurakuntaan liitettiin Suomussalmen ja Puolangan kappelit, jotka erotettiin itsenäisiksi kirkkoherrakunniksi 1856 ja 1867. Seurakuntaan kuulunut Ristijärven kappeli erotettiin itsenäiseksi seurakunnaksi 1896.
Maakirjakylät
Hyrynsalmi (Salmen kylä), Kytömäki, Luvankylä, Moisiovaara, Oravivaara, Tapanivaara
Naapuriseurakunnat
Papisto
Kirkkoherran vastikejyvät 3,02 hehtolitraa viljaa peräytettiin keisarillisen senaatin päätöksellä 18.2.1896.
Kirkkoherrat
1786–1802 Johan Petri Snellman
1803–1845 Johan Wegelius
1847–1849 Karl Saxa
1853–1856 Gustaf Vilhelm Appelgren
1858–1869 Gustaf Adolf Saxbäck
1870–1880 Jonas Kristian Castrén
1881–1891 Johan Fredrik Lindbäck
1891–1915 Jonas Eliel Snellman, ensin vt. kirkkoherra
1921–1955 Toivo Pekka Liimatta
Kappalaiset
1786–1788 Johan Appelgren
1792–1808 Erik Ekdahl, siirrettiin Ristijärvelle
Apupapit ja armovuodensaarnaajat
1788–1789 Johan Boman
1801–1804 Peter Kristian Snellman
Ylimääräiset papit
1818–1819 Adolf Forbus, kirkkoherran apulainen
1820–1826 Julius Alexander Krank, kirkkoherran apulainen
1826–1830 Frans Isak Fortell, kirkkoherran apulainen
1829–1833 Julius Abraham Vidgrén, kirkkoherran apulainen
1833–1834 Jakob Fredrik Liljeblad, kirkkoherran apulainen
1834–1836 Jakob Arvid Frosterus, kirkkoherran apulainen
1836–1839 Karl Adolf Eberhardt, kirkkoherran apulainen
1839–1848 Johan Vegelius, kirkkoherran apulainen, vt. kirkkoherra
1848–1849 Robert Mellin, kirkkoherran apulainen
1849–1853 Karl Otto Tenlén, vt. kirkkoherra
1856–1858 Johan Lagus, vt. kirkkoherra
1880 Samuel Abraham Strömmer, vt. kirkkoherra
1880–1881 Konrad Ferdinand Melartin, vt. kirkkoherra
1901 Kaarlo Emil Kalli, vt. kirkkoherra
1909 Kaarlo Väinö Johannes Pfaler, vt. kirkkoherra
1909– Johan William Hirvonen, vt. kirkkoherra
1915–1921 Toivo Pekka Liimatta, vt. kirkkoherra
Arkisto
Hyrynsalmen seurakunnan rippikirjat alkavat vuodesta 1786, tilikirjat vuodesta 1787 ja historiakirjat vuodesta 1787. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1733–1951.
Kansallisarkisto on digitoinut Hyrynsalmen seurakunnan vanhimmat kirkonkirjat noin 1860-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.