Kuolajärven alue kuului alkuaan Kuusamoon ja siirrettiin Kemijärven itsenäistyneeseen seurakuntaan 1776. Kuolajärven Lappia varten asetettiin katekeetta keisarillisella käskykirjeellä 6.11.1821. Seurakunta muodostettiin kappeliksi, kun kappalaisen palkasta tehtiin suostumus 26.9.1824 ja alueen asukkaiden anomukseen omasta kirkosta suostuttiin 4.3.1826. Kirkon rakentamista ja virkatalon kuntoon laittamista varten annettiin valtion varoja keisarillisella käskykirjeellä 25.4.1834. Seurakuntaan määrättiin katekeetta keisarillisella käskykirjeellä 13.12.1845 ja toinen 11.10.1882.
Erotettiin Kemijärvestä itsenäiseksi kirkkoherrakunnaksi keisarillisella käskykirjeellä 30.11.1857. Tie Kemijärven ja Kuolajärven välille valmistui 1898. Kinkerimatkoilla pidettiin kahdesti vuodessa jumalanpalvelus pitäjän kulmilla. Kuolajärven kunta perustettiin 1857. Kunnan ja seurakunnan nimi muutettiin Sallaksi 1936.
Sallasta luovutettiin 5 834 neliökilometrin alue Neuvostoliitolle 19.9.1944 solmitun välirauhansopimuksen mukaan. Luovutettuun alueeseen kuuluivat kokonaan tai osittain kunnallisena keskuksena toiminut Sallansuun kylä sekä Alakurtin, Korjan, Kuolajärven, Lampelan, Sovajärven, Tuutijärven, Vuorijärven, Vuosnajärven ja Yläkurtin kylät. Sallalaisia evakuoitiin sotavuosina lähinnä Kälviän ja Kaustisen seuduille. Välirauhan jälkeen Sallasta evakuoiduista suurin osa asutettiin maanhankintalain perusteella Sallan ja Kuusamon alueille. Sallan kunnalliseksi keskukseksi tuli Märkäjärven kylä, jonne rakennettiin seurakunnan uusi pääkirkko. Myöhemmin vuonna 1963 ja 1964 kirkot rakennettiin myös Hautajärvelle sekä Kursuun.
Muut nimet
Salla
Maakirjakylät
Aatsinki, Ahola, Ahvenselkä, Hautajärvi, Kallunki, Korja, Kuolajärvi, Kursu, Kurtti, Lampela, Lapajärvi, Liikanen, Märkäjärvi, Naruska, Niemelä, Onkamo, Oulanka, Pahkakumpu, Paloperä, Saija, Sallansivu, Sallansuu, Salmivaara, Selkälä, Sovajärvi, Tuohikylä, Tuutijärvi, Vallovaara, Varvikko, Vuorijärvi
Naapuriseurakunnat
Papisto
Kirkkoherran kruununpalkka oli alussa 15 tynnyriä ohria ja 85 ruplaa 80 kopeekkaa. Palkkaa korotettiin 200 ruplalla keisarillisella käskykirjeellä 23.1.1862 ja 800 markalla 5.11.1873. Vuonna 1898 kirkkoherran palkka oli 1 943 markkaa 20 penniä, 810 kiloa voita, 107,75 hehtolitraa ohraa, 322 kappaletta juustoja, 322 peurapaistia, 94 markkaa maahanlaskuista, 360 oravannahkaa, 184 markkaa sportteleita sekä 300 markkaa virkatalosta, eli yhteensä 5 916 markkaa.
Kirkkoherrat
1862–1867 Erik Johan Eriksson
1869–1870 Johan Fredrik Thauvón
1875–1888 Johan Gustaf Sipilä
1889–1904 Viktor Johan Gabriel Krogerus
1905–1921 Aukusti Hakkarainen
1921–1928 Uuno Ilmari Hietalahti
1928–1934 Lauri Arvi Matias Kivekäs, vt. kirkkoherra
1934–1972 Erkki Koivisto
Kappalaiset
1839–1852 Kristian Vilhelm Litzell
1852–1859 Henrik Krank
Rajaseutupapit Hautajärvellä
1945–1946 Sulo A. Isokoski
1946 Erkki Ervamaa
1947–1948 Mauno A. Kytömäki
1948–1950 Martti Hyvärinen
Ylimääräiset papit
1859–1862 Johan Immanuel Bergh, vt. kappalainen, vt. kirkkoherra
1867–1869 Johan Fredrik Thauvón, välisaarnaaja
1875 Antti Hulkkonen, vt. kirkkoherra
1888–1889 Per Robert Matias Heikel, vt. kirkkoherra
1904 Per Robert Matias Heikel, vt. kirkkoherra
1946 Jorma Sipilä
1946–1949 Sulo A. Isokoski
1948 Maunu Kytömäki
1949–1950 Martti Hyvärinen
Arkisto
Kuolajärven eli Sallan seurakunnan rippikirjat alkavat vuodesta 1832. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa. Seurakunnan päättävien elinten toiminnasta ennen vuotta 1928 kertovat pöytäkirjat tuhoutuivat sotien aikana.
Kansallisarkisto on digitoinut Kuolajärven 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.