Perustettiin Pudasjärven emäseurakunnan Jokijärven rukoushuonekunnaksi keisarin suostuttua rukoushuoneen rakentamiseen Pudasjärven Kurjen kylän Taivalkosken sahan läheisyyteen 22.6.1842. Toisen rukoushuoneen rakentamiseen Jokijärven puolelle anottiin samalla lupaa, mutta tähän ei tiettävästi annettu vastausta. Tuomiokapitulin määräyksen mukaan papillisen katekeetan tai Pudasjärven papiston apulaisen tuli pitää uudessa rukoushuoneessa jumalanpalveluksia erikseen määrätyssä järjestyksessä. Ensimmäinen kirkko valmistui Jokijärven kylään 1848 ja se siirrettiin Taivalkosken kylään 12.4.1877 annetulla päätöksellä. Kirkon siirto toteutui 1878. Muodostettiin Pudasjärven emäseurakunnan Jokijärven kappeliksi keisarillisella käskykirjeellä 16.1.1858 ja erotettiin itsenäiseksi Taivalkosken kirkkoherrakunnaksi 27.8.1879. Taivalkosken osia liitettiin perustettuun Posion seurakuntaan 1908, mikä toteutui 1925. Kirkko paloi salaman sytyttämänä perustuksiaan myöden 27.7.1925. Taivalkosken kunta perustettiin 1878 ja siihen liitettiin vuonna 1868 perustettu Jokijärven kunta 1884.
Muut nimet
Jokijärvi
Kylät
Jokijärvi, Jokikylä, Jurmu, Kurtti, Loukusa, Metsäkylä, Taivalkoski, Vaarakylä
Naapuriseurakunnat
Papisto
Kirkkoherran virkatalon oikeuksista annettiin keisarillinen käskykirje 20.10.1892.
Kirkkoherrat
1888–1908 Johan Barkman
1912–1913 Juho Viktor Kiviharju
1914–1926 Johan Valfrid Teräsvaara
Kappalaiset
1880–1884 Gustaf Edvard Nyman, virka lakkautettiin
Ylimääräiset papit
1842–1850 Johan Peter Lithovius, saarnaajakatekeetta
1850–1853 Johan Bäckvall, saarnaajakatekeetta
1853–1858 Karl Otto Tenlén, saarnaajakatekeetta
1853 Karl Otto Tenlén, vt. kappalainen
1858–1862 Nils Fellman, vt. kappalainen
1875–1876 Alfred Elieser Backman, vt. kappalainen
1876 Herman Hannula, vt. kappalainen
1878–1880 Gustaf Edvard Nyman, vt. kappalainen
1884–1885 Antti Lappalainen, vt. kirkkoherra
1885–1887 Johan Barkman, vt. kirkkoherra
1909–1912 Yrjö Henrik Kortekangas, vt. kirkkoherra
Arkisto
Taivalkosken seurakunnan rippikirjat alkavat vuodesta 1850 ja historiakirjat vuodesta 1875. Vanhemmat tiedot löytyvät Pudasjärven kirkonkirjoista. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1849–1860.
Kansallisarkisto on digitoinut Taivalkosken 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.