Perustettiin Paltamon emäseurakunnan kappeliksi 1764. Siirrettiin kuuluvaksi Hyrynsalmen seurakuntaan 1786 ja sai oman kappalaisen 1788. Erotettiin Hyrynsalmesta itsenäiseksi kirkkoherrakunnaksi keisarillisella käskykirjeellä 11.11.1867. Seurakunnan vuonna 1792 rakennettu kirkko korjattiin perusteellisesti 1893. Puolangan kunta perustettiin 1867 ja kuntaan liitettiin osia Säräisniemestä 1921.
Muut nimet
Auho, Puolango, Puolanko
Maakirjakylät
Aittokylä, Askankylä, Auho, Joukokylä, Kotila, Lylykylä, Oterma, Puokio, Puolanka, Rasi, Suolijärvi, Väyrylä
Naapuriseurakunnat
Papisto
Kirkkoherran vastikejyvät 2,75 hehtolitraa viljaa peräytettiin keisarillisen senaatin päätöksellä 7.2.1896, jolloin seurakunnalle määrättiin uusi palkkausjärjestys.
Kirkkoherrat
1870–1876 Johan Fredrik Thauvón
1878–1881 Gustaf Adolf Snellman
1882–1890 Fredrik Mennander
1891–1904 Oskari Vilho Oksanen
1905–1908 Henrik Fabian Kärki
1912–1917 Paavo Hamunen, nimitettiin virkaan 1909
1921–1935 Väinö Johannes Tanskanen
1935–1943 Toivo Vilho Kultimo Laitinen
1944–1956 Antti Ilmari Hakala
Kappalaiset
1788–1804 Johan Petterson
1805–1811 Nils Fellman
1813–1843 Petter Ervast
1844–1869 Gustaf Lövenmark, virka lakkautettiin
Apupapit ja armovuodensaarnaajat
1837–1840 Johan Gabriel Vilander
Ylimääräiset papit
1802–1805 Erik Johan Snellman, kappalaisen apulainen
1811–1813 Jonas Mellin, välisaarnaaja
1840–1844 Johan Henrik Ervast, vt. kirkkoherra
1861 Isak Vilhelm Krank, vt. kappalainen
1869–1870 Nils August Berghäll, välisaarnaaja
1876–1877 Johan Fredrik Lindbäck, välisaarnaaja
1877–1878 Erik Snellman, välisaarnaaja
1881–1882 Kondrad Ferdinand Melartin, välisaarnaaja
1890–1891 Antti Adolf Gummerus, vt. kirkkoherra
1904 Jonas Eliel Snellman, vt. kirkkoherra
1904–1905 Arvid Esaias Ruuskanen, vt. kirkkoherra, välisaarnaaja
1908 Väinö Erkki Viljanen, vt. kirkkoherra
1908–1910 Väinö Johannes Tanskanen, vt. kirkkoherra
1910 F. J. Berg, vt. kirkkoherra
1910–1912 Matti Kauppinen, vt. kirkkoherra
1911 Kyösti Kauppinen, vt. kirkkoherra
1916 Wäinö Pöysti, vt. kirkkoherra
1917 Alfred Wirkkula, vt. kirkkoherra
1919 Emil Rechardt, vt. kirkkoherra
1920–1922 Eero Johannes (Hannes) Hyvärinen, vt. kirkkoherra
1935 Olavi Laitinen, vt. kirkkoherra
1940 Arvi Takala, vt. kirkkoherra
1943–1946 Uuno Johannes Tuppurainen, vt. kirkkoherra, apulainen
1942 Eino Ojajärvi, vt. kirkkoherra
Arkisto
Puolangan seurakunnan rippikirjat alkavat vuodesta 1789, tilikirjat vuodesta 1789 ja historiakirjat vuodesta 1789. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1789–1948.
Kansallisarkisto on digitoinut Puolangan 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.