Perustettiin Salon emäseurakunnan rukoushuonekunnaksi sen jälkeen kun Pehkolan eli Paavolan kylän asukkaiden luvatta itselleen rakentama kirkko määrättiin vihittäväksi kuninkaallisella käskykirjeellä 16.10.1691. Salon neljänneskuntaan mainittiin 1688 rakennetun kaksi saarnatupaa, toinen Luohualle, jonne Paavolan kylän asukkaat tulivat, ja toinen Vihantiin, joissa tuvissa Salon papisto piti jumalanpalveluksia suurina pyhinä ja ehtiessään muulloinkin. Pulkkilassa siihen asti asunut Siikajoen pitäjänapulainen siirrettiin Paavolaan 1702. Kirkko kärsi vaurioita isonvihan aikana. Paavolan asukkaat saivat oikeuden itse kutsua pitäjänapulaisena kuninkaan päätöksellä 30.5.1793. Muodostettiin kappeliseurakunnaksi hallitsevan konsistorin päätöksellä 5.11.1811 ja pitäjänapulainen sijoitettiin Revonlahdelle. Kirkkoa laajennettiin 1856. Erotettiin Siikajoesta itsenäiseksi kirkkoherrakunnaksi keisarillisella käskykirjeellä 9.9.1874, mutta ero toteutui vasta 1.5.1899, ja ensimmäisen kirkkoherran Fredrik Mennanderin oli määrä virkaansa 1.5.1890, mutta kuoli vähän ennen tätä. Seurakuntaan kuulunut Ruukin rukoushuonekunta perustettiin 1912. Paavolan kunta yhdistettiin Revonlahden kanssa Ruukin kunnaksi 1973 ja samalla seurakunnat yhdistyivät Paavolan seurakunnaksi, jonka nimi muutettiin Ruukin seurakunnaksi 1992.
Muut nimet
Luohua, Pehkola
Kylät
Lappi, Luohua, Pehkola, Ruukki
Naapuriseurakunnat
Papisto
Kirkkoherran vastikejyvöt 3,57 hehtolitraa viljaa peräytettiin keisarillisen senaatin päätöksellä 7.12.1894.
Kirkkoherrat
1890 Fredrik Mennander, kuoli ennen virkaan astumistaan
1892–1900 Vilhelm Malmivaara (Malmbeg)
1901–1921 Konrad Ferdinand Melartin
1923–1929 Matti Haikola
Kappalaiset
1812–1853 Johan Lagus
1856–1861 Johan Mikael Stenbäck
1864–1877 Johan Lagus, virka lakkautettiin
Pitäjänapulaiset
1724–1739 Johan Brandberg, Paavolan ja Pulkkilan kappalainen
1724–1739 Petter Schroderus
1739–1745 Johan Simelius
1746–1753 Anders Blåholm
1754–1776 Jakob Flander
1777–1807 Jakob Mannerström
Ylimääräiset papit
1776–1777 Jakob Mannerström, apulaispappi
1807–1812 Erik Ganander, armovuodensaarnaaja, välisaarnaaja
1830–1834 Nils Frosterus, kappalaisen apulainen
1834–1839 Karl Fredrik Meurling, kappalaisen apulainen
1834–1841 Karl Fredrik Meurling, kappalaisen apulainen
1841 Nils Fellman, kappalaisen apulainen
1842–1844 Johan Krank, kappalaisen apulainen
1844–1856 Johan Lagus nuor., kappalaisen apulainen, armovuodensaarnaaja
1861–1864 Emil August Wichmann, armovuodensaarnaaja
1877–1878 Nils Gustaf Emeleus, vt. kappalainen
1878–1882 Karl Heinemann, vt. kappalainen
1882–1883 Niilo Karlsberg, vt. kappalainen
1883–1887 Erik Snellman, vt. kappalainen
1887–1890 Jonatan Gummerus, vt. kappalainen
1890–1892 Henrik August Wichmann, vt. kirkkoherra
1897–1898 Alfred Riihimäki, kirkkoherran apulainen
1899 Matias Aleksanteri Nikkilä, vt. kirkkoherra, Revonlahden vt. kappalainen
1899 Johan Abram Pietola, kirkkoherran apulainen
1900–1901 Kaarle Zefanias Simelius, vt. kirkkoherra
1901 Rurik Calamnius, vt. kirkkoherra
1920–1922 Erkki Vuornos
1922–1923 Olli Morttinen
1929 Iisakki Koukkari
1929–1931 Verner Ruskomaa
Arkisto
Paavolan seurakunnan rippikirjat alkavat vuodesta 1733, tilikirjat vuodesta 1693 ja historiakirjat vuodesta 1733. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1564–1954.
Kansallisarkisto on digitoinut Paavolan seurakunnan vanhimmat kirkonkirjat noin 1870-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.