Erotettiin Limingan emäseurakunnasta itsenäiseksi Oulujärven seurakunnaksi 1559, mutta liitettiin jälleen Liminkaan noin 1581, kun venäläiset ryöstivät pitäjän, polttivat Manaman saarella sijainneen kirkon ja murhasivat papin. Kutsuttiin alkuaan Oulun erämaaksi ja 1600-luvun alussa Kajaanin pitäjäksi. Perustettiin uudelleen itsenäisenä kirkkoherrakuntana, kun tänne määrättiin uusi kirkkoherra ja tämän palkaksi määrättiin 24 tynnyriä kruununviljaa 12.2.1599. Uusi kirkko rakennettiin Paltaniemelle, jonka mukaan seurakuntaa alettiin kutsua Paltamoksi, vaikka pitäjää kutsutaankin vanhoilla nimillä vielä 1650. Pitäjässä ilmoitettiin olevan 30 saarnapaikkaa 1688. Seurakunnassa oli kappalaisia yksi ainakin 1615-1648, kaksi 1648-1694 sekä kolme 1694-1783, joista yksi siirrettiin Säräisniemelle 1783 ja toinen Kajaaniin 1787. Seurakunnan keskus siirrettiin Paltaniemeltä Kiehimään 1936, jonne valmistui uusi kirkko 1946.
Seurakuntaan kuulunut Kajaani erotettiin itsenäiseksi kirkkoherrakunnaksi 1651, mutta yhdistettiin anneksina Paltamoon kuninkaallisella käskykirjeellä 23.1.1786. Koska Kajaani oli ollut luonteeltaan kuninkaallinen pitäjä, muutettiin koko Paltamo sekä Hyrynsalmen konsistoriaalinen seurakunta saman luontoisiksi kuninkaallisella käskykirjeellä 19.11.1804. Seurakuntaan kuulunut Sotkamo erotettiin itsenäiseksi kirkkoherrakunnaksi 1647 ja Säräisniemi 1864. Seurakuntaan 1764 perustetut Suomussalmen ja Puolangan kappelit yhdistettiin Hyrynsalmeen, kun se erotettiin itsenäiseksi kirkkoherrakunnaksi 1786. Kajaani erotettiin uudelleen itsenäiseksi kirkkoherrakunnaksi 1897. Paltamon kunta perustetiin 1870.
Seurakunnan järjestyksessään toinen kirkko vahingoittui pahasti maanjäristyksessä Eskilin päivänä 1626, jonka jälkeen rakennettiin uusi kirkko. Seurakunnan vuonna 1665 rakennettu kirkko joutui venäläisten ryöstämäksi 1712 ja polttamaksi 1716, jonka jälkeen rakennettiin nykyinen Paltaniemen kaksinkertainen kirkko 1726 ja varustettiin seinämaalauksilla. Isonvihan aikana kirkon lisäksi poltettiin kellotapuli ja pappila. Venäläiset hyökkäsivät ensi kerran ryöstäen pappilaa 13.3.1712 ja kirkon ryöstön vahingot arvioitiin 3000 kuparitaalariksi.
Muut nimet
Oulujärvi, Paldamo, Ulo erämark, Uloträsk, Ulåträsk
Kylät
Härmänmäki, Kiehimä, Kivesjärvi, Melalahti, Mieslahti, Paltaniemi, Uura, Varisniemi (Varesniemi)
Naapuriseurakunnat
Papisto
Kirkkoherran karjakymmenyksistä tehtiin suostumus 5.8.1733, jonka maaherra vahvisti 25.1.1736. Kuninkaallisella kirjeellä 25.10.1757 säädettiin, että Kajaanin kirkkoherralla ja kaikilla Kajaanin läänin kappalaisilla oli oikeus lukea kaksinkertaiset virkavuodet, mikä oikeus lakkautettiin kuninkaallisella käskykirjeellä 3.9.1800. Kirkkoherrat menettivät tämän oikeuden keisarillisella käskykirjeellä 30.6.1847. Paltamon, Hyrynsalmen ja Sotkamon pitäjiin asetettiin yksi lastenopettaja kuhunkin keisarillisella käskykirjeellä 1.9.1830. Kirkkoherran 4,78 hehtolitran vastikejyvät peräytettiin keisarillisen senaatin päätöksellä 19.5.1897.
Kirkkoherrat
1559–1580 Olaus Laurentii Rahikainen
1599–1614 Gregorius Petri Hordelius
1614–1615 Benedictus Mathæus Petraeus
1616–1620 Simon Erici Frosterus
1620–1628 Mansvertus Jacobi Fellman
1628–1644 Matthias Laurentii Björneburgensis
1644–1651 Samuel Thomæ Paldanius
1651–1660 Johan Matthiæ Antilius
1660–1703 Johannes Andreæ Cajanus
1703–1716 Ericus Johannis Cajanus
1720–1726 Abraham Jacobi Frosterus
1727–1742 Simon Pauli Forström
1742–1747 Anders Andreae Cajanus
1749–1751 Erik Munselius
1752–1774 Jakob Salmenius
1776–1784 Simon Appelgren
1786–1803 Gabriel Matias Lescelius
1806–1831 Karl Fredrik Aejmelaeus
1832–1858 Karl Aejmelaeus
1859–1882 Anders Andelin
1884–1920 Fredrik Rechardt
1920–1936 Kustaa Emil Roine
Kappalaiset, ensimmäinen sarja
1610–1616 Mansvertus Jacobi Fellman
1618 Matthias Georgii
1620–1628 Matthias Laurentii Tammelin (Björnburgensis?)
1628–1641 Gabriel Christiani Limingius
1641–1644 Samuel Thomæ Paldanus
1644–1651 Johannes Matthiæ Antilius
1661–1672 Petrus Petri Prochæus
1672–1686 Ericus Fortelius
1686–1691 Abrahamus Falander
1691–1711 Johannes Petri Prochæus
1712–1716 Ericus Erici Cajanus
1722–1740 Johan Eriki Cajanus
1742–1747 Isak Erici Sinius
1750–1773 Isak Fortelius
1774–1789 Ericus Erici Frosterus
1790–1806 Karl Fredrik Aejmelaeus
1807–1817 Gustaf Johannis Frosterus
1819–1825 Anders Engelberg
1827–1835 Karl Aejmelaeus
1835–1839 Berndt Gustaf Hällsten
1839–1870 Adolf Forbus
1873–1892 Johan Gabriel Vilander
1894–1900 Tahvo Martikainen
1901–1909 Antero Vartiainen
1910–1915 Väinö Johannes Pfaler
1915–1930 Johan William Hirvonen
Kappalaiset, toinen sarja
1651–1660 Johannes Andreæ Cajanus
1660– Johannes Samuelsis Paldanus
1678–1703 Ericus Johannis Cajanus
1705–1736 Casper Groen
1736–1737 Erik Johannis Brax
1738–1744 Jakob Abrahami Frosterus
1744–1776 Simon Appelgren
1777–1793 Gustaf Reinhold Appelgren, virka siirrettiin Säräisniemelle 1783
Kappalaiset, kolmas sarja
1694–1712 Andreas Jeremiæ Cajanus
1712–1736 Johan Brax
1738–1758 Mikael Forsberg
1759–1786 Johan Wichman, virka muutettiin Kajaanin kappalaisen viraksi
Apupapit ja armovuodensaarnaajat
1737–1739 Johan Wervenius
1749– Johan Freitag
1751– Petter Groen
1785–1786 Johan Wichman
1817–1819 Johan Gerhard Snellman
1872–1873 Nils Viktor Nordlund
1892–1894 Tapani Martikainen
Ylimääräiset papit
1729–1735 Erik Brax, kappalaisen apulainen
1739 Isak Sinius, kirkkoherran apulainen
1754–1759 Johan Wichman, kappalaisen apulainen
1755– Erik Castrén, kirkkoherran apulainen
1760– Mikael Montin, kirkkoherran apulainen
1763– Simon Achrenius, kirkkoherran apulainen
1764– Karl Henrik Ståhle, kirkkoherran apulainen
1765– Erik Frosterus, kappalaisen apulainen
1774–1777 Gustaf Reinhold Appelgren, kirkkoherran apulainen
1778–1779 Isak Schroderus, kappalaisen apulainen
1780– Johan Appelgren, kirkkoherran apulainen
1793– Gustaf Durchman, kirkkoherran apulainen
1797–1800 Matthias Törnudd, kirkkoherran apulainen
1803–1806 Karl Fredrik Aejmelaeus, kirkkoherran apulainen
1818–1827 Karl Aejmelaeus, kirkkoherran apulainen
1827–1835 Karl Adolf Eberhardt, kirkkoherran apulainen, armovuoden saarnaaja
1850–1853 Johan Peter Bäckman, kirkkoherran ja kappalaisen apulainen
1853–1855 Frans Fredrik Lönnrot, kirkkoherran ja kappalaisen apulainen, välisaarnaaja
1859–1860 Frans Fredrik Lönnrot, kirkkoherran ja kappalaisen apulainen, välisaarnaaja
1854–1858 Karl Adolf Forbus, kappalaisen apulainen
1858 Johan Vilhelm Murman, papin apulainen, välisaarnaaja
1858–1859 Anders August Krank, välisaarnaaja
1860–1866 August Johan Frosterus, kappalaisen apulainen
1867–1870 Adolf Jakob Teodor Skogman, kappalaisen apulainen
1873–1875 Vilhelm Adrian Mandellöf, kirkkoherran apulainen
1875 Peter Vilhelm Harald, kirkkoherran apulainen
1875–1877 Gustaf Edvard Nyman, kirkkoherran apulainen
1878–1880 Oskar Hjalmar Valdemar Fabritius, kirkkoherran apulainen
1880–1884 Kaarle Johan Vartiainen, kirkkoherran apulainen, armovuodensaarnaaja
1887–1888 Eljas Lönnrot, vt. kirkkoherra
1888 Juhana Viktor Savolainen, kirkkoherran apulainen
1893–1901 Antero Vartiainen, vt. kirkkoherra
1906–1908 Väinö Erkki Viljanen, kirkkoherran apulainen, vt. kirkkoherra
Arkisto
Paltamon seurakunnan rippikirjat alkavat vuodesta 1731, tilikirjat vuodesta 1681 ja historiakirjat vuodesta 1727. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1618–1923.
Kansallisarkisto on digitoinut Paltamon 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.