Kuolajärven alue kuului alkuaan Kuusamoon ja siirrettiin Kemijärveen itsenäistyneeseen seurakuntaan 1776. Kuolajärven Lappia varten asetettiin katekeetta keisarillisella käskykirjeellä 6.11.1821 ja muodostettiin kappeliksi, kun kappalaisen palkasta tehtiin suostumus 26.9.1824 ja alueen asukkaiden anomukseen omasta kirkosta suostuttiin 4.3.1826. Kirkon rakentamiseen 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ä omaksi 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 ja kunnan ja seurakunnan nimi muutettiin Sallaksi 1936.
Sallan kunta menetti lähes puolet pinta-alastaan Neuvostoliitolle 1944. Sallalaiset olivat evakossa Kälviän ja Kaustisen seudulla. Sotien jälkeen seurakunnan keskukseksi tuli Märkäjärven kylä, jonne rakennettiin pääkirkko, Myöhemmin omat kirkot vamistuivat Hautajärvelle 1963 ja Kursuun 1964.
Muut nimet
Salla
Kylät
Aatsinki, Ahola, Hautajärvi, Hietajärvi, Kallunki, Käsmä, Korja, Kuolajärvi, Kursu, Kurtti, Lampela, Märkäjärvi, Niemelä, Onkamo, Paloperä, Saija, Sallansuu, Salmijärvi, Selkälä, Sovajärvi, Tenniö, Tuutijärvi, Vuorijärvi
Naapuriseurakunnat
Papisto
Kirkkoherran kruununpalkka oli alussa 15 tynnyriä ohria ja 85 ruplaa 80 kopeekkaa, ja palkkaa korotettiin 200 ruplaa 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 maahanlaskusita, 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
Kappalaiset
1839–1852 Kristian Vilhelm Litzell
1852–1859 Henrik Krank
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
Arkisto
Kuolajärven eli Sallan seurakunnan rippikirjat alkavat vuodesta 1832. Seurakunnan vanhinta arkisto säilytetään Kansallisarkisto Oulussa. Seurakunnan päättävien elinten toiminnasta ennen vuotta 1928 kertovat pöytäkirjat tuhoutuivat sotien aikana.