Kemin kirkkoherra Johannes Tuderus toimitti Kuusamossa joulukuussa 1685 rovastintarkastuksen, jonka yhteydessä seurakuntalaiset antoivat lupauksen kirkon rakentamisessa tarvittavien hirsien hankkimisesta jo saman talven aikana. Seurakunnan ensimmäinen kirkkorakennus, väliaikainen ns. saarnatupa valmistui sitten Torangintaipaleelle. Sijaintipaikka oli nykyisestä kirkosta 2,5 kilometriä etelä-kaakkoon Tolpanniemen ja Kuusamojärven välisellä kannaksella. Valmistumisvuosi oli 1689. Tämän pienen saarnahuoneen yhteyteen valmistui myös pappila vuonna 1691. Seurakuntaa alettiin vuonna 1692 kutsua keskuspaikkansa nimellä Kuusamon Lapin seurakunnaksi.
Seurakunta perustui 1600-luvun lopulla lappalaisväestön sijaan yhä kasvavassa määrin seudulle muuttavan uudisasutuksen varaan. Uudisasutus oli varsin ekspansiivista jo 1680-luvulla ja kirkkoherra Cajanus pyrki voimakkaasti edistämään sitä. Edellä mainitun rovastintarkastuksen pöytäkirja mainitsee alueella tuolloin asuneen arviolta 34 perhettä ja 194 ihmistä.
Varsinaisen kirkkorakennuksen suunnittelu ja toteutus alkoi 1690-luvulla seurakunnan kolmannen kirkkoherran Samuel Juleniuksen aikana. Kirkko rakennettiin seurakuntalaisten ja kirkkoherran välisen kiistan jälkeen uudelle, nykyiselle kirkon paikalle Kirkkolahden Samostenperän rannalle. Kirkko valmistui vuonna 1694 ja vihittiin käyttöön 1695. Kirkon pituus ja leveys olivat 17,22 ja korkeus 5,94 metriä. Seurakunnan historiateoksen mukaan vuonna 1760 valmistunut Inarin kappelikirkko Pielpajärvellä on todennäköisesti ollut samankaltainen kirkkorakennus. Kirkkoherran pappilaksi ostettiin 1700-luvun alussa Sigfrid Boneliuksen virkakaudella kirkon vieressä sijainnut talonpoikaistalo.
Kyseinen kirkko alkoi käydä jo 1750-luvulle tultaessa ahtaaksi, ja mittava korjaustyö toteutettiin vuosina 1767–1768. Kirkon ahtaus nousi ongelmaksi edelleen 1780-luvulla ja rovastintarkastuksessa 1787 kuultiin kehotus uuden kirkon rakentamisesta.
Uuden kirkon rakentaminen on todennäköisesti alkanut vuonna 1798 ja se vihittiin käyttöön 26.2.1804. Uusi kirkko oli edeltäjäänsä huomattavasti suurempi pituuden ollessa 36,82 ja leveyden 34,44 metriä. Kirkkoon mahtui kerralla 1200 ihmistä.
Vuonna 1935 kirkkoon valmistui suurempi remontti, ja tässä yhteydessä kirkko sai keskuslämmityksen. Tämä niin kutsuttu ”vanha kirkko” tuhoutui vuonna 1944 toisen maailmansodan yhteydessä.
