Sotkamon seudulle Savosta ja Pohjanmaalta tulleet asukkaat kuuluivat alkuaan Oulujärven seurakuntaan ja oman kirkon puuttuessa asukkaat kävivät kirkossa Paltaniemellä tai aiemmin jopa Manamansalossa. Seudulla mainitaan olleen oma saarnatupa ja pappi ainakin jo 1630. Kainuun kaakkoisosat erotettiin Oulujärven eli Paltamon emäseurakunnasta itsenäiseksi pitäjäksi 1647. Seurakunnassa ilmoitettiin olevan noin 20 saarnapaikkaa 200 taloa varten 1668. Mielipuoli sytytti kirkon palamaan 1692 ja kirkon kunnostamiseksi koottiin kolehtia 1693. Kappalaisen pappila paloi 1804. Seurakuntaan kuulunut Kuhmoniemen eli Kuhmon kappeli erotettiin itsenäiseksi kirkkoherrakunnaksi 1856. Sotkamon nykyinen kirkko, joka on järjestyksessään viides, valmistui Johan Oldenburgin suunnitelmien mukaan 1870. Keisarillinen senaatti määräsi seurakunnan jaettavaksi kahdeksi kirkkoherrakunnaksi ja Jormasjärven kirkkoherrakunnan perustettavaksi Sotkamon lounaisista osista 11.5.1897, mutta päätös peruttiin 1908. Sotkamon kunta perustettiin 1874.
Maakirjakylät
Alasotkamo, Jormaskylä, Korholanmäki, Laaka, Lahnasjärvi, Nuasjärvi, Sumsa, Tipasoja, Ylisotkamo
Naapuriseurakunnat
Papisto
Suostumus papiston palkasta tehtiin 15.5.1749 ja 18.6.1779, jolloin nauriskymmenykset maksettiin oravan nahoissa. Kappalaisen palkasta tehtiin suostumus 3.6.1787, jonka maaherra vahvisti 12.7.1787. Kirkkoherran vastikejyvät 6,32 hehtolitraa viljaa peräytettiin keisarillisen senaatin päätöksellä 11.5.1897. Sotkamon ja Kuhmoniemen kappalaisilla oli kaksinkertaiset virkavuodet kuninkaallisella käskykirjeellä 24.11.1757. Tämä oikeus lakkautettiin keisarillisella käskykirjeellä 30.6.1847.
Kirkkoherrat
1647–1650 Mansvetus Jacobi Fellman
1651–1691 Ericus Andreae Cajanus
1692–1712 Ericus Erici Cajanus
1714–1727 Isaacus Isaaci Sinius
1728–1734 Abraham Sadenius
1736–1744 Casper Groen
1746–1755 Lars Henrik Backman
1756–1762 Johan Lagus
1764–1809 Johan Frosterus
1811–1833 Gabriel Johannis Lagus
1836–1841 Karl Henrik Rislachi
1844–1847 Johan Reinhold Appelgren
1849–1867 Karl Benjamin Ståhlberg
1861–1881 Reinhold Helander
1884–1885 Kaarlo Heinemann
1889–1892 Nils Holmström
1896–1913 Henrik Mustakallio (Schwartzberg)
1917–1933 Eljas Lönnroth
1935–1939 Toivo Aapeli Janhonen
1941–1949 Mauri Veikko Tena
Kuhmoniemen kappalaiset ennen kappelin perustamista
–1689 Andreas Erici Cajanus
1690–1714 Isaacus Sinius
1714–1744 Josephus Ahllund
1745–1753 Joseph Ahllund, nuorempi
Kappalaiset
1647–1651 Ericus Andreae Cajanus
1652–1672 Henricus Johannis Hoffrenius
1672–1691 Ericus Erici Cajanus
1693–1714 Zacharias Uhlbrandt
1714–1721 Ericus Mathiae Svahn
1722–1726 Ericus Isaaci Sinius
1727–1734 Jacobus Chydenius
1735–1762 Henricus Melanus
1763–1785 Samuel Bohm
1786–1806 Isaac Schroderus
1807–1819 Gabriel Ståhlberg
1823–1860 Johan Petterson
1863–1876 Gustav Reinhold Petterson
1876–1887 Kristian Kekoni
1888–1917 August Mömmö
1919–1929 Max Alfrid Wilhelm Katavisto
1931–1958 Jafet Räty
Ylimääräiset papit ja saarnaajat
1630–1646 Mansvetus Jacobi Fellman, saarnaaja
1734–1736 Jakob Frosterus, armovuodensaarnaaja
1745 Isak Sinius, armovuodensaarnaaja
1747–1749 Samuel Anglén, kirkkoherran apulainen
1751–1758 Daniel Cajanus, kirkkoherran apulainen
1755– Sven Olsbo, kappalaisen apulainen
1790–1791 Jakob Frosterus, kirkkoherran apulainen
1794–1807 Gustaf Frosterus, kirkkoherran apulainen
1807 Jonas Gustaf Högman, vt. kappalainen, välisaarnaaja 1808
1807–1811 Petter Ervast, kirkkoherran apulainen
1811–1819 Henrik Josef Bergh, kappalaisen apulainen
1819–1823 Karl Benjamin Ståhlberg, kappalaisen apulainen, armovuodensaarnaaja
1826–1828 Julius Alexander Krank, kirkkoherran apulainen
1830–1832 Matias Forsberg, kirkkoherran apulainen
1831 Nils Fellman, kappalaisen apulainen
1832–1837 Johan Jakob Ingman, kirkkoherran apulainen, armovuodensaarnaaja
1836–1837 Jakob Fredrik Liljeblad, kappalaisen apulainen
1837–1839 August Kranck, kirkkoherran ja kappalaisen apulainen
1841 August Kranck, kirkkoherran ja kappalaisen apulainen
1838–1841 Johan Carpen, kirkkoherran ja kappalaisen apulainen
1839–1841 Johan Sandell, kappalaisen apulainen
1841–1844 Gustaf Löwenmark, sijaiskirkkoherra
1844–1847 Abraham Neuman, kirkkoherran apulainen
1845–1863 Gustaf Reinhold Petterson, kappalaisen sijainen ja apulainen
1857–1858 Johan Gabriel Ståhlberg, kirkkoherran apulainen
1881–1882 Kaarlo Huotari, kirkkoherran apulainen, virkavuodensaarnaaja
1882–1884 August Mömmö, armovuodensaarnaaja
1885–1888 Mikko Liukku, sijaiskirkkoherra, armovuodensaarnaaja
1887–1889 Lauri Arvid Itkonen, armovuodensaarnaaja
1893–1894 Anders Vartiainen, vt kirkkoherra
1896–1897 Pekka Airaksinen, kirkkoherran apulainen
1897–1898 Niilo Aleksanteri Huttunen, kirkkoherran apulainen
1898–1901 Kaarlo Emil Kalli, kirkkoherran apulainen
1907–1908 Kustaa Kylänpää, kirkkoherran apulainen
1908– Emil Juho Hallikainen, kirkkoherran apulainen, vt. kirkkoherra
Arkisto
Sotkamon seurakunnan rippikirjat alkavat vuodesta 1683, tilikirjat vuodesta 1719 ja historiakirjat vuodesta 1729. Osa kirkonarkistosta lienee palanut 1866. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1683–1948.
Kansallisarkisto on digitoinut Sotkamon 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.