1600-luvun alussa Kaarle IX pyrki asuttamaan Lappia uudisasukkailla. Hän halusi toimia alueen väestön hengellisen elämän kohottamiseksi. Kuningatar Kristiinan toimesta rakennettiin vuonna 1646 ensimmäiset kirkot Kemijärvelle ja Inariin.

23.9. 1688 kuningas Kaarle IX myönsi Sodankylän kirkon rakentamiseen omista käyttövaroistaan 900 kuparitaalaria. Samana vuonna päätettiin Sodankylän kappeliseurakunnan perustamisesta Kemin Lapin kirkkoherrakuntaan. Hirsikirkko valmistui 1689.

Sodankylä määrättiin omaksi kirkkoherrakunnaksi 1747 ja silloinen kappalainen Henrik Wegelius nimitettiin Sodankylän seurakunnan ensimmäiseksi kirkkoherraksi. Seurakunnan alue käsitti tuolloin Sodankylän, Sompion, Keminkylän (=Savukoski ja Pelkosenniemi) ja Kittilän kylät. Väkeä alueella oli noin 700 henkeä.

Vuonna 1854 erotettiin Kittilä ja vuonna 1916 Pelkosenniemi ja Savukoski omiksi seurakunniksi. Näistä Pelkosenniemi ja Savukoski yhdistettiin keskenään v. 1930 Pelkosenniemen seurakunnaksi.

Seurakunnan väkimäärän kasvaessa tuli ajankohtaiseksi uuden isomman kirkon rakentaminen. 1852 keisari Nikolai I hyväksyi uuden kirkon rakennettavaksi valtion varoilla. Keisari Aleksanteri II puolestaan hyväksyi 1856 kirkon piirustukset. Uusi kivikirkko valmitui 1859.