Alkuaan osa Kemin Lappia, josta erotettiin itsenäiseksi kirkkoherrakunnaksi 1675. Tällöin siihen kuuluivat myös Sodankylän ja Inarin alueet. Kahden kappalaisen asettaminen Kuusamoon ja Sodankylään mainitaan kuninkaallisessa päätöksessä 25.10.1688. Seurakunnan saamelaisten käännyttämisestä päätettiin 3.10.1723 ja asiaa varten asetettiin erillinen toimikunta valtiopäivillä 18.4.1739. Aluksi Kemin kirkkoherralle oli uskottu rovastintehtävät Lapinmaan seurakunnissa, mutta tuomiokapituli antoi 1758 luvan määrätä asiaa varten jonkin kontrahdin taitavimmista kirkkoherroista. Seurakunta siirrettiin Kemin rovastikunnasta Oulun rovastikuntaan keisarillisella käskykirjeellä 9.6.1849. Kuusamon kunta perustettiin 1868 ja muodostettiin kaupungiksi 2000.
Seurakuntaan kuulunut Sodankylä perustettiin kappeliksi 1689 ja erotettiin itsenäiseksi kirkkoherrakunnaksi. Inari liitettiin kappelina Utsjoen emäseurakuntaan 1747. Kuolajärven käräjäkunta erotettiin ja liitettiin perustettuun Kemijärven emäseurakuntaan 1776. Seurakunnan osia liitettiin perustettuun Posion seurakuntaan 1908.
Seurakunnan ensimmäinen kirkko rakennettiin Torankijärven rannalle 1680. Kirkko ilmeisesti paloi 1692, jolloin määrättiin kannettavaksi kolehti "för den arme meeningheten i Lappmarken wedh Kuusamo" 2.7.1692. Seuraava kirkko valmistui 1694.
Kuusamosta luovutettiin 1 653 neliökilometrin alue Neuvostoliitolle 19.9.1944 solmitun välirauhansopimuksen mukaan. Alue käsitti kokonaan tai osittain Enojärven, Kenttiylän, Paanajärven, Pukarin, Tavajärven ja Vatajärven kylät. Kuusamolaisia evakuoitiin sotavuosina lähinnä Pudasjärven, Saloisten ja Yli-Iin alueille sekä Oulun eteläpuolisille paikkakunnille. Evakuoiduista noin 60 prosenttia palasi takaisin Kuusamoon 1944 välirauhan jälkeen.
Maakirjakylät
Alakitka, Heikkilä, Kirkonkylä, Lämsä, Posio, Poussu, Vasaraperä
Naapuriseurakunnat
Papisto
Kuusamossa ja muissa Lapin seurakunnissa palvelleet papit saivat kuninkaan kirjeen 16.1.1757 mukaan oikeuden tulla kuninkaalle esitetyiksi kirkkoherroiksi johonkin kuninkaalliseen kirkkoherrakuntaan poislukien kaupungit ja sellaiset seurakunnat, joilla oli erioikeuksia. Kuusamon, Utsjoen ja Sodankylän kirkkoherroille suotiin vaaliehto- ja virkaylennysoikeus keisarin käskykirjeellä 30.5.1817. Oikeus ei kuitenkaan koskenut suurimpia tai ensimmäiseen luokkaan kuuluneita seurakuntia, elleivät kirkkoherrat olleet tunnettuja erinomaisesta opista ja taidosta. Mainitun käskykirjeen mukaan kirkkoherrat saivat hakemus- ja virkaoikeuden, jos olivat hoitaneet virkaansa taidolla ja innolla Lapissa Utsjoen kirkkoherrana kahdeksan vuotta, Sodankylän kirkkoherrana 10 vuotta tai Kuusamon kirkkoherrana 12 vuotta. Kirkkoherroilla oli myös kuninkaan 11.10.1792 suoma oikeus tulla tuomiokapitulin esittämäksi ja nimitettäväksi ansiollisuuden ja taidollisuuden mukaan. Nämä etuoikeudet vahvistettiin keisarin käskykirjeellä 30.6.1847. Kuitenkin armollisen kirjeen 31.12.1881 mukaan Kuusamon seurakunta sai oikeuden vastedes kutsua kirkkoherransa tuomiokapitulin kirkkolain säätämässä järjestyksessä tekemän ehdollepanon jälkeen vaalin kautta.
Kirkkoherra sai keisarillisella käskykirjeellä 12.12.1816 myönnytyksen, että ne kruununkymmenykset, 40 tynnyriä ja yhdeksän ruplaa 60 kopeekkaa, jotka hän siihen asti oli saanut nauttia, tästä lähtien tulisivat hänelle vakinaiseksi palkaksi luetuiksi. Myöhemmin kuitenkin määrättiin, että kirkkoherran kruununtihunti, 65,92 hehtolitraa ohria sekä 33 markan 20 pennin kuljetusmaksu, oli vastaisuudessa peräytettävä vastikerahastoon. Kirkkoherran palkka oli Keisarillisen senaatin päätöksen 7.10.1880 mukaan 72 tynnyriä viljaa, yksi naula voita lehmältä, yksi leipä, yksi juusto sekä kuivattuja haukia ja lihaa joka talolta. Lisäksi yhteensä 700 markkaa virkatalosta, 32 markkaa 90 penniä rahassa, 1 122 kiloa voita, 59,36 hehtolitraa rukiita, 125,31 hehtolitraa ohraa, juuustoa ja leipää, lihaa 930 markkaa 50 penniä rahassa, pääsiäisrahaa 910 markkaa, maahanlaskulta lehminä 540 markkaa sekä 480 markkaa sportteleita. Kirkkoherran palkka oli rahassa yhteensä 7 300 markkaa.
Keisarillisella käskykirjeellä 18.6.1828 säädettiin, että seurakuntaan asetettaisiin papiksi vihitty kiertävä lastenopettaja tai katekeetta. Tällä olisi 100 ruplan kruununpalkka, jota korotettiin 50 ruplalla käskykirjeellä 2.5.1845. Toinen katekeetta määrättiin vuodeksi 600 markan palkalla keisarillisella käskykirjeellä 9.10.1889 ja edelleen viideksi vuodeksi 5.10.1893. Kolmannesta katekeetasta keisarin käskykirje 1.9.1897.
Kirkkoherrat
1675–1684 Gabriel Johannis Tuderus
–1691 Henricius Cajanus
1691–1699 Samuel Julenius
1699–1716 Sigfridus Bonelius
1719–1733 Zacharias Forbus
1734–1746 Jacob Chydenius
1748–1784 Johan Alexandri Kranck
1784–1800 Johan Kranck
1801–1816 Eric Castrén
1817–1825 Abraham Montin
1825–1833 Johan Gustaf Costiander
1836–1870 Johan Gustaf Krank
1872–1875 Herman Ingman
1877–1880 Johan Lagus
1881–1894 Viktor Vilhelm Wichmann
1895– Antti Adolf Valtavaara (Gummerus), ensin vt. kirkkoherra
1919–1950 Lauri Konstantin Eerola
Apupapit ja armovuoden saarnaajat
1799–1800 Gustaf Durchman
1894–1895 Pekka Rudolf Heikel
Ylimääräiset papit
1747–1748 Petter Svebilius, vt. kirkkoherra
1759 Nils Fellman, vt. kirkkoherra
1759 Elias Lagus, kirkkoherran apulainen
1773–1774 Anders Törnudd, kirkkoherran apulainen
1774–1784 Johan Kranck, kirkkoherran apulainen
1783 Elias Kranck, kirkkoherran apulainen
1800–1801 Jakob Wichman, virka- ja armovuodensaarnaaja
1801–1803 Johan Henrik Kranck, armovuodensaarnaaja, kirkkoherran apulainen
1804–1812 Jakob Castrén, kirkkoherran apulainen
1812–1814 Mikael Österberg, kirkkoherran apulainen
1814–1815 Olof Vallin, kirkkoherran apulainen
1815–1816 Johan Nordberg, kirkkoherran apulainen
1816–1817 Johan Vilhelm Holmberg, kirkkoherran apulainen
1830–1840 Johan Fredrik Planting, kirkkoherran apulainen, katekeetta
1840–1873 Johan Gabriel Vilander, kirkkoherran apulainen, sijainen ja katekeetta
1858–1860 Anders Abraham Favorin, kirkkoherran sijainen
1875–1877 Nils Johan Lukander, virka- ja armovuodensaarnaaja
1875 Alfred Elieser Backman, virka- ja armovuodensaarnaaja
1880–1881 Juho Tanskanen, välisaarnaaja
1890–1891 Juho Korhonen, kirkkoherran sijainen
1891–1893 Kaarle Reetrikki Sorri, vt. kirkkoherra
1894 Henrik Niiranen
Arkisto
Kuusamon seurakunnan rippikirjat alkavat vuodesta 1760, tilikirjat vuodesta 1755 ja historiakirjat vuodesta 1730. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1681–1957.
Palosta, jossa vanhin arkisto näyttää tuhoutuneen, on ilmoitus pitäjänkokouksen pöytäkirjassa 20.6.1760: "Förestältes nödwändigheten af de i wintras genom en wädelig eld obrukbare gjorde prästgårds spisars snara uplagander, hwartil en karl af hwart byalag blef unnämnd til den 29 hujus". Uuden pappilan kunnostamisesta päätettiin kokouksessa 8.4.1749: "Widtaltes om den nya Bygningen som under Hr Kyrckioherdens Chydenii tid och efter hans afwikning för 6 åhr sedan blifwit upsatt, men så illa och obeqwämt indelt, at man haft betänckande, om hon är wärd at inredas och fullbyggas; dock som socknen giordt sitt til och är oskyldig uti inrättningen, blef öfwerens kommit at byggningen skulle förfärdigas och hwar för sin andel skulle skaffa til materialier som behöfdes". Kokouksessa 29.7.1753 edelleen mainitaan: "Gafs af Pastore tilkänna hwad wid den nya Byggningen ännu stod at laga med antydan at det dagen derpå skulle blifwa wärkstält. åmintes om nödig reparation på den gamla Byggningen i synnerhet getäckningen med ny näfwer och takwed". Vanhasta pappilasta todetaan 17.4.1761: "Föreställtes huru bristfällig Prästegårds gamla byggning wore med begäran at den åtminstone skulle å nyo täckas, hwilket sochne männerna låfwade göra sedan arbetet följande dagen blifwit dem emellan tillbörligen utdelt".
Palo sattui siis pappilan uudessa rakennuksessa kevättalvella 1760. Myöhemmän tiedon mukaan palossa ei tiettävästi tuhoutunut arkistoa. Aiemmin 9.4.1730 pappila oli sitä vastoin palanut nopeasti syttyen perustuksiaan myöten arkistoineen. Seurakunnan historiakirjat alkavat tämän aiemman palon jälkeisestä vuodesta 1730.
Kansallisarkisto on digitoinut Kuusamon 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.