Alkuaan Salon emäseurakunnan kappeli, joka erotettiin kuuluvaksi Liminkaan noin 1477 ja siirrettiin Oulun seurakuntaan 1610. Seurakunnassa mainitaan olleen kaksi kappalaista 1688, jotka toimittivat jumalanpalveluksia kymmenessä paikassa eri puolilla pitäjää, ja heistä toinen siirrettiin Utajärven perustettuun kappeliin 1762. Erotettiin Limingasta itsenäiseksi kirkkoherrakunnaksi kuninkaallisella käskykirjeellä 20.8.1766. Ensimmäisen Kirkkosaarella sijainneen tai toisen Kirkonniemellä sijaitsevan kirkon sanotaan kertomusten mukaan venäläisten polttaneen. Isonvihan aikana venäläiset ryöstivät nykyisestä kirkosta kellot ja muun irtaimen omaisuuden. Seurakuntaan kuulunut Utajärven kappeli erotettiin itsenäiseksi kirkkoherrakunnaksi 1886. Muhoksen kunta perustettiin 1865.
Kylät
Kylmälä, Laitasaari, Muhos, Pyhänsivu
Naapuriseurakunnat
Papisto
Kirkkoherran vastikejyvät 12,46 hehtolitraa viljaa peräytettiin keisarillisen senaatin päätöksellä 21.5.1892.
Kirkkoherrat
1769–1776 Israel Nicolai Aejmelaeus
1778–1789 Isaac Ervast
1791 Abraham Enqvist
1794–1812 Gustaf Reinhold Appelgren
1814–1819 Johan Wichman
1823–1854 Karl Jakob Frosterus
1857–1880 Samuel Strömmer
1881–1896 Gustaf Adolf Snellman
1899– Samuel Abraham Strömmer
Kappalaiset, ensimmäinen sarja
1630–1647 Abraham Erici Bong
1651 Andreas Cajanus
1673–1698 Ericus Sigfridi Brax
1698–1731 Isak Gisselkors
1733–1762 Gabriel Ståhlberg, virka siirrettiin Utajärvelle
Kappalaiset, toinen sarja
1672–1694 Andreas Salander
1695–1726 Johannes Palmannus
1727–1732 Henrik Carlenius
1734–1759 Johan Svahn
1760–1797 Mathias Salow
1798–1812 Nils Peter Cajaner
1814–1826 Erik Johan Snellman
1829–1873 Johan Zakris Cajaner
1876–1890 Karl Algot Hanell
1890–1900 Erik Pesonen
1900–1908 Niilo Iisakki Simelius
1909– Yrjö Heikki Simelius
Ylimääräiset papit
1733–1734 Johan Svan, kappalaisen viran armovuodensaarnaaja
1752–1754 Johan Uhlman, kappalaisen apulainen
1754– Gabriel Lagerberg, kappalaisen apulainen
1757– Matthias Salow, kappalaisen apulainen
1764 Benjamin Ståhlberg, kappalaisen apulainen
1772–1773 Anders Törnudd, kappalaisen apulainen
1776– Johan Pettersson, kappalaisen apulainen
1779– Johan Boman, kappalaisen apulainen
1789– Johan Gummerus, kirkkoherran viran armovuodensaarnaaja
1795–1796 Jakob Cajanus, kappalaisen apulainen
1801–1806 Johan Lagus, kirkkoherran apulainen
1806–1810 Johan Reinhold Appelgren, kirkkoherran apulainen
1811–1813 Per Samuel Heikel, kirkkoherran apulainen, sijaiskirkkoherra
1812 Johan Petterson, armovuodensaarnaaja
1812–1814 Nils Peter Cajaner, armovuodensaarnaaja, sijaiskirkkoherra
1814–1822 Johan Zakris Cajaner, kirkkoherran apulainen
1826–1829 Gustaf Adolf Hornborg, vt. kappalainen
1827–1829 Johan Jakob Ingman, kirkkoherran apulainen
1830–1831 Salomon Albert Möller, kirkkkoherran apulainen
1831–1833 Lars Henrik Törnqvist, kirkkoherran apulainen
1833–1834 Julius Abraham Vidgrén, kirkkoherran apulainen
1834–1842 Johan Peter Lithovius, kirkkoherran apulainen
1842–1843 Karl Heikel, kirkkoherran apulainen
1843–1844 Abraham Neuman, kirkkoherran apulainen
1844–1846 Gustaf Zakris Ramstadius, kappalaisen apulainen
1844–1848 Jakob Aulin, kirkkoherran apulainen
1848–1849 Frans Henrik Hällfors, kirkkoherran apulainen
1849–1852 Robert Mellin, kirkkoherran apulainen
1852–1854 Karl Immanuel Hällfors, kirkkoherran apulainen
1854–1857 Adolf Jakob Teodor Skogman, kirkkoherran apulainen, sijaiskirkkoherra
1857–1858 Abraham Vilhelm Hackzell, kirkkoherran apulainen
1872–1876 Karl Algot Hanell, vt. kappalainen
1877 Samuel Abraham Strömmer, kirkkoherran apulainen
1878–1879 Viktor Gideon Aulin, kirkkoherran apulainen
1903 Paavo Emil Snellman, kirkkoherran apulainen
Arkisto
Muhoksen seurakunnan rippikirjat alkavat vuodesta 1699, tilikirjat vuodesta 1722 ja historiakirjat vuodesta 1722. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1630–1930.
Kansallisarkisto on digitoinut Muhoksen 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.