Alkuaan Tohmajärven emäseurakunnan kappeli, perustettu ennen 1693, jolloin paikkakunnalla oli jo pieni Pyhän Marian ristikirkko. Venäläiset ryöstivät kirkon isonvihan aikana 1708. Tohmajärven toinen kappalainen hoiti jumalanpalveluksia seurakunnassa, kunnes kappalainen muutti seurakuntaan 1757. Kun virkatalo oli hankittu, kappalainen sijoitettiin seurakuntaan 2.11.1783. Seurakunnassa oli pitäjänapulainen 1805–1812 ja Tohmajärven kirkkoherra velvoitettiin palkkaamaan virallisen apulaisen kappelia varten keisarillisella käskykirjeellä 12.11.1838. Erotettiin itsenäiseksi kirkkoherrakunnaksi keisarillisella käskykirjeellä 4.5.1857, jolloin se määrättiin kirkkoherran ja pitäjänapulaisen hoidettavaksi. Seurakunnan osista erotettiin Pyhäselän itsenäinen kirkkoherrakunta 1911.
Kellotapuli paloi ukkosen sytyttämänä 25.7.1813 ja siitä on seuraava merkintä: "25 Juli å en söndag under Gudstjänsten slog åskan ner å kyrkogården antände den nya och välmålade klockstapeln, hvilken med dess 2:ne välljudande klockor uppbrann och förstördes. En bondehustru, Mickel Johansson Koljonens Susanna Heiskain. från Paloby blef till döds slagen, flere personer uti kyrkan blefvo af en åskvigge skadde, som inkom genom stora dörren och tog vägen ut genom utgången från sakristian." Pappilassa paoli tulipalo 4.6.1921, jolloi tuhoutui kaikki muut rakennukset paitsi pappilan päärakennus, riihi, sauna, sikala ja ladot.
Muut nimet
Pyhän Marian kappeli, S:t Maria kapell
Kylät
Heinävaara, Huuhtilampi, Keskijärvi, Kiihtelysvaara, Oskola, Palo, Röksä, Uskaljärvi
Naapuriseurakunnat
Papisto
Kirkkoherrat
1896–1924 William Wartiovaara (Veckman)
1925–1948 Juho Noponen
Kappalaiset
1783–1786 Johan Argillander
1786–1797 Johan Petrelius, ensin vt. kappalainen
1829–1830 David Petrelius
1833–1847 Nils Aschan
1850–1857 Samuel Strömmer
1858–1877 Erik Kristian Relander, virka lakkautettiin
Pitäjänapulaiset
1805–1812 Johan Lagus
1880–1903 David Hakkarainen
1908–1913 Emil Nyholm
1913–1919 Juho Silvennoinen
Apupapit ja armovuodensaarnaajat
1783–1786 Johan Argillander
1800–1802 Johan Lagus, kappalaisen apulainen
1813–1819 Johan Petrelius nuorempi, kappalaisen apulainen
1819–1820 Klas Anders Lindblad, kappalaisen apulainen
1820–1829 David Petrelius, kappalaisen apulainen
1830–1832 August Vilhelm Krogerus, armovuodensaarnaaja
1832–1833 August Blomqvist, armovuodensaarnaaja
1841–1845 Jonas Gabriel Grahn, (Tohmajärven) kirkkoherran apulainen
1845–1846 Karl Liljeqvist, kirkkoherran apulainen
1846–1847 Lars August Blom, kirkkoherran apulainen
1847–1858 Peter Jakob Igoni, kirkkoherran apulainen, vt. kirkkoherra
1857–1859 Johan Jakob Strömmer, kirkkoherran apulainen
1859–1862 Nils August Berghäll, kirkkoherran apulainen
1876 Johan Tanskanen, kirkkoherran apulainen
1876–1877 Otto Alfred Malmgren, kirkkoherran apulainen
1877–1879 Adam Laitinen, kirkkoherran apulainen
1878 Aukusti Koivisto, kirkkoherran apulainen
1879–1880 David Hakkarainen, armovuodensaarnaaja
1880–1889 Iisakki Puustinen, kirkkoherran apulainen
1889–1895 Herman Salomon Kuosmanen, kirkkoherran apulainen
1783–1786 Johan Argillander, apupappi
1903–1906 Antero Juhana Räty, armovuodensaarnaaja
1914–1919 Antero Juhana Räty, apupappi
1914–1915 Kaarlo Mela
Ylimääräiset papit
1895–1896 Antero Juhana Räty, vt. pitäjänapulainen, armovuosisaarnaaja
1907 Onni Oskari Hämäläinen, vt. pitäjänapulainen ja armovuosisaarnaaja
1907–1908 Johan Edvard Niemi, vt. pitäjänapulainen, välisaarnaaja
Arkisto
Kiihtelysvaaran seurakunnan rippikirjat alkavat vuodesta 1746, tilikirjat vuodesta 1750 ja historiakirjat vuodesta 1785. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Joensuussa ja aineistokokonaisuus kattaa vuodet 1742–1952.
Kansallisarkisto on digitoinut Kiihtelysvaaran seurakunnan vanhimmat kirkonkirjat noin 1870-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.