Perustettiin Paltamon emäseurakunnan kappeliksi sen jälkeen kun, kuningas oli 29.3.1764 suostunut siihen, että Suomussalmen Alannon ja Puolangan Auhon kulmille rakennettaisiin omat kirkot. Hyrynsalmi erotettiin itsenäiseksi kirkkoherrakunnaksi kuninkaan käskykirjeellä 23.1.1786, jolloin määrättiin sekä Alannon eli Hulkonniemen että Puolangan kirkoille asetettavaksi omat vakituiset kappalaiset ja Paltamon kirkkoherran yhden vuoden tulot annettiin näiden kirkkorakennusten avuksi. Suomussalmi erotettiin Hyrynsalmesta itsenäiseksi kirkkoherrakunnaksi keisarillisella käskykirjeellä 26.6.1856. Seurakuntaan kuulunut Vuokin alue määrättiin erotettavaksi itsenäiseksi kirkkoherrakunnaksi 1919, mutta määräys peruttiin, sillä uusi seurakunta oli vielä järjestäytymättä 1935. Suomussalmen kunta perustettiin 1867.
Muut nimet
Alanto, Hulkonniemi, Kianto
Kylät
Alajärvi, Alanäljänkä, Alavuokki, Kerälä, Kianta, Kirkonkylä, Pesiö, Piispajärvi, Ruhtinaansalmi, Ylinäljänkä, Ylivuokki
Naapuriseurakunnat
Papisto
Kirkkoherran vastikejyvät 3,13 hehtolitraa viljaa peräytettiin keisarillisen senaatin päätöksellä 31.1.1896.
Kirkkoherrat
1870–1875 Emanuel Snellman
1879–1915 August Benjamin Calamnius
1916–1917 Filip Nordlund
1917–1935 Toivo Aapeli Janhonen
Kappalaiset
1786–1821 Karl Saxa, vanhempi
1822–1847 Karl Saxa, nuorempi
1848–1867 Karl Adolf Lilius
1884–1892 Gustaf Edvard Nyman
1895–1912 Paavo Hamunen
1912–1921 Taavetti Kapiainen
1923–1949 Kaarlo August Piironen
Apupapit ja armovuodensaarnaajat
1877–1881 Johan Fredrik Lindbäck
Ylimääräiset papit
1792–1811 Johan Gerhard Snellman, vt. kappalainen
1813–1817 Jonas Mellin, kappalaisen apulainen
1817–1819 Anders Engelberg, kappalaisen apulainen
1819–1822 Karl Saxa nuor., kappalaisen apulainen, vt. kappalainen
1825–1833 Johan Ahlholm, kappalaisen sijainen, apulainen
1827 Johan Jacob Ingman, kappalaisen apulainen
1833–1834 Josef Vilhelm Durchman, kappalaisen apulainen
1834–1836 Jacob Fredrik Liljeblad, kappalaisen apulainen
1837–1843 Jacob Arvid Frosterus, kappalaisen apulainen
1844–1847 Thure Birger Wegelius, kappalaisen apulainen,
1847–1848 Johan Henrik Ervast, kappalaisen apulainen, välisaarnaaja
1854–1857 Mikael Adolf Pelkonen, kappalaisen apulainen
1857–1858 Johan Wegelius, apulainen
1858–1859 Frans Niklas Lackström, kirkkoherran apulainen
1859–1861 Isak Vilhelm Kranck, kappalaisen apulainen
1862–1866 Johan Gabriel Ståhlberg, kirkkoherran apulainen
1866–1867 Johan Mauritz Sonck, kappalaisen apulainen
1867–1870 Emanuel Snellman, vt. kappalainen, vt. kirkkoherra
1875–1877 Erik Snellman, vt. kirkkoherra, vt. pitäjän apulainen
1883–1884 Antti Lappalainen, vt. pitäjän apulainen
1892–1895 Paavo Hamunen, vt. pitäjän apulainen
1896–1899 Rurik Calamnius, kirkkoherran apulainen
1902–1903 Rurik Calamnius, kirkkoherran apulainen
1899–1902 Johan Nikolai Mecklin, kirkkoherran apulainen
1905–1909 Olof Peter Kyyhkynen, kirkkoherran apulainen
1909–1910 Matti Kauppinen, kirkkoherran apulainen
1915–1916 Oskari Jussila, vt. kirkkoherra
1921–1923 Toivo Aapeli Janhonen, vt. kappalainen
Arkisto
Suomussalmen seurakunnan rippikirjat alkavat vuodesta 1787, tilikirjat vuodesta 1859 ja historiakirjat vuodesta 1786. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1787–1900.
Kansallisarkisto on digitoinut Suomussalmen 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.