Alkuaan Iin emäseurakunnan kappeli, joka erotettiin itsenäiseksi kirkkoherrakunnaksi ensimmäisen kirkkoherran valtakirjalla 26.2.1639, jonka kuningas vahvisti 13.10.1641. Tuolloin Hiltulan tila myönnettiin kirkkoherran virkataloksi ja kreivi Per Brahe antoi sille virkatalon oikeudet 30.3.1649. Seurakuntaan kuulunut Jokijärven rukoushuonekunta muodostettiin kappeliksi 1858 ja erotettiin itsenäiseksi Taivalkosken kirkkoherrakunnaksi 1879. Pudasjärvestä liitettiin osia perustettuun Ranuan emäseurakuntaan 1894 ja perustettuun Posion emäseurakuntaan 1908, joista ensiksi mainittu aloitti toimintansa 1917 ja viimeksi mainittu toteutui 1925. Pudasjärven kunta perustettiin 1865 ja muodostettiin kaupungiksi 2004.
Seurakunnan ensimmäisen kirkon väitetään kirjallisuudessa rakennetun jo 1500-luvulla. Nykyinen kirkko rakennettiin 1781. Kirkko syttyi tuleen 7.8.1914, mutta palo saatiin estetyksi.
Muut nimet
Yli-Ii, Över Ijo
Kylät
Hetejärvi, Iinattijärvi, Jonku, Kollaja, Korpinen, Kurki, Kylät, Livo, Naamanka, Pudasjärvi, Puhos, Sarajärvi, Siurua, Sotkajärvi
Naapuriseurakunnat
Kuivaniemi, Posio, Puolanka, Ranua, Suomussalmi, Taivalkoski, Utajärvi, Ylikiiminki, Yli-Ii
Papisto
Seurakunnan nauriskymmenykset suoritettiin oravannahoissa vielä 1840-luvulla. Seurakunnan papiston oikeudesta hyväkseen kaksinkertaiset virkavuodet annettiin kuninkaallinen päätös 3.9.1800, mutta oikeus lakkautettiin keisarillisella käskykirjalla 30.6.1847. Katekeetta tai papiston virallinen apulainen määrättiin asetettavaksi keisarillisella käskykirjeellä 3.4.1840, ja hänet määrättiin hoitamaan Jokijärven rukoushuonetta, jonka rakentamiselle Pudasjärven Kurjen kylään annettiin armollinen lupa 22.6.1842. Entinen kappalaisen virkatalo Parkkila vaihdettiin Lievetmursun tilaan keisarillisella käskykirjeellä 1.12.1837. Keisarillisen Senaatin päätöksen 16.1.1858 mukaan seurakunnan tuli itse palkata katekeetta, jos sellaiselle opettajalle oli tarve.
Kirkkoherrat
1639–1666 Josephus Josephi Palmannus
1667–1685 Daniel Danielis Anglenius
1686–1688 Samuel Samuelis Lithovius
1689–1691 Johan Wegelius
1691–1706 Johannes Olai Keckman
1707–1726 Ericus Frosterus
1727–1737 Barthold Ervast
1739–1740 Johan Brandberg
1742–1761 Samuel Johannis Keckman
1763–1785 Erik Castrén
1786–1809 Johan Frosterus
1811–1824 Isak Montin
1825–1838 Abraham Montin
1838–1846 Elias Efraim Alcenius, ensin vt. kirkkoherra
1850–1854 Herman Magnus Inberg
1855–1867 Lars Herman Laurin
1870–1871 Robert Vilhelm Montin
1872–1880 Karl Immanuel Hällfors
1883–1889 Karl Abiel Heikel
1892–1901 Viktor Alfred Virkkula
1902–1917 Emil Thauvón
1918–1941 Juho Kipinä
Kappalaiset
1639 Josephus Josephi Palmannus, vanhempi
1639–1666 Josephus Josephi Palmannus, nuorempi
1667 Daniel Anglenius
1667–1777 Andreas Palmannus
1678–1791 Johannes Keckman
1691–1725 Daniel Danieli Anglenius
1725–1733 Gabriel Ståhlberg
1733–1777 Jeremias Stenius
1778–1809 Gabriel Petri Calamnius
1811–1838 Johan Henrik Kranck
1843–1850 Herman Magnus Inberg
1851–1870 Robert Vilhelm Montin
1870–1871 Johan Immanuel Bergh
1873–1878 Gustaf Adolf Snellman
1879–1905 Paavo Martikainen
1905–1910 Oskar Immanuel Heikel
1910–1928 Arvid Esaias Ruuskanen, virka lakkautettiin 1922
Apupapit ja armovuodensaarnaajat
1806–1811 Efraim Wilhelm Snellman, kappalaisen apulainen, armovuoden saarnaaja
1836–1843 Gustaf Vilhelm Appelgren, kappalaisen sijainen, armovuodensaarnaaja, välisaarnaaja
1848–1851 Karl Johan Forsström, armovuodensaarnaaja, välisaarnaaja
1867–1869 Nils August Berghäll, armovuodensaarnaaja
1869–1870 Kristian Kekoni, armovuodensaarnaaja
Ylimääräiset papit
1732–1733 Mikael Forsberg, kirkkoherran apulainen
1732–1733 Jeremias Stenius, kirkkoherran apulainen
1744–1750 Kristian Henrik Keckman, kirkkoherran apulainen
1752–1765 Anders Hägg, kirkkoherran apulainen
1757–1765 Isak Stenius, kappalaisen apulainen
1766–1771 Lars Samuel Keckman, kappalaisen apulainen
1772–1777 Johan Thurin, kappalaisen apulainen
1779–1786 Karl Saxa, kirkkoherran apulainen
1805–1809 Johan Pettersson, kirkkoherran apulainen
1806–1811 Efraim Wilhelm Snellman, kappalaisen apulainen
1809 Jakob Frosterus, kirkkoherran apulainen
1824–1825 Ernst Vilhelm Frosterus, välisaarnaaja
1827–1829 Julius Kristian Becker, kirkkoherran apulainen
1829–1832 Erik August Montin, kirkkoherran apulainen
1833–1836 Erik August Montin, kappalaisen apulaisen sijainen
1836–1843 Gustaf Vilhelm Appelgren, kappalaisen sijainen, armovuodensaarnaaja, välisaarnaaja
1846–1848 Robert Vilhelm Montin, välisaarnaaja, kirkkoherran sijainen
1848–1851 Karl Johan Forsström, armovuoden saarnaaja, välisaarnaaja
1854–1855 Oskar Elis Petterson, välisaarnaaja
1867 Karl Alfred Calamnius, vt. kirkkoherra
1871–1872 Johan Gustaf Sipilä, vt. kirkkoherra ja kappalainen
1878–1879 Gustaf Edvard Nyman, vt. kappalainen
1889–1892 Jonas Eliel Snellman, vt. kirkkoherra
Arkisto
Pudasjärven seurakunnan rippikirjat alkavat 1700-luvun alusta, tilikirjat vuodesta 1679 ja historiakirjat vuodesta 1686. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1666–1930.