Ennen Kemin Lapin seurakunnan perustamista 1673 sen alueella asusti lappalaisväestöä, jota oli jo ryhdytty käännyttämään kristinuskoon Kemin seurakunnan pappien toimesta. Oletetaan, että lähes kaikki Kuusamon lappalaiset olisivat tulleet kastetuiksi Kemin kirkkoherran Johannes Pictoriuksen (1630–1643) aikana. Kemin seurakuntaan valmistuivat vuonna 1646 Kemijärven ja Inarin kappelikirkot, joiden papit Jakob Lapodius ja Esaias Fellman hoitivat kirkollisia tehtäviä myös Kitkan ja Maaselän lapinkylissä ennen uuden Kemin Lapin seurakunnan perustamista.
Ruotsin kuningas Kaarle XI antoi Turun piispalle määräyksen Kemin Lapin seurakunnan perustamisesta 21.6.1673. Määräykseen sisältyi myös tulevan seurakunnan kirkkoherran nimi, Gabriel Tuderus, joka oli tuohon aikaan Inarin kappalainen. Turun piispa määräsi kirjeessään 3.9.1673 seuraavat Lapin kylät erotettaviksi Kemin seurakunnasta uuteen perustettuun seurakuntaan: Inari, Kemikylä (nyk. Savukoski ja Pelkosenniemi), Kittilä, Kuolajärvi, Sodankylä, Sompio, Kuolajärvi, Kitka ja Maanselkä.
Uuden seurakunnan syntyä tuettiin 27.9.1673 kuninkaan asetuksella – Lapin plakaatilla. Sen tavoitteena oli edistää alueen uudisasutusta houkuttelemalla ruotsalaisia ja suomalaisia talonpoikia uudisasukkaiksi Lappiin määräaikaisella verovapaudella ja vapautuksella sotaväkeen otosta. Määritetyn alueen keskellä sijaitsi Kemin seurakunnan Kemijärven kappeli, joka oli saanut papin jo vuonna 1646.
Ensimmäinen kirkkoherra Gabriel Tuderus hoiti tehtäväänsä Alatorniosta käsin ja hänet nimitettiinkin kyseisen pitäjän kirkkoherraksi 1682. Seuraaja, vuonna 1684 kirkkoherraksi tullut Henricus Cajanus pyrki siihen, että seurakunnan keskus rakennettaisiin Kuusamoon.
Seurakunnan alkuvaiheeseen liittyi vuosikymmenten ajan vakiintumattomuutta ja monenlaisia ongelmia. Alue oli vähäväkistä ja köyhää. Seurakunta oli laaja ja papin ja seurakuntalaisten tapaamiset satunnaisia. Uudisasutus kaskitalouksineen tuhosi lappalaisten elämäntavan ja elinkeinojen harjoittamisen. Seurauksena oli vastakkainasettelu ja käräjöinti.
Nälkävuodet 1696–1697 olivat vakava koettelemus asutukselle. Sekä lappalaisten kyliä että uudistiloja autioitui. Isonvihan aika 1700-luvun alussa toi paikkakunnalle levotonta ja säädytöntä elämää viettävää väestöä. Kuusamon seurakunnan historia (S. Ervasti 1981) kuvaa aikaa näin: ”Vanha patriarkaalinen lappalaisyhdyskunta voimakkaine perhe- ja sukuyhteisöineen hajosi ja lappalaiset tunsivat itsensä juurettomiksi, toisaalta taasen hajallaan asuvat uudistilalliset eivät olleet vielä muodostaneet järjestäytynyttä yhdyskuntaa”.