Perustettiin Säräisniemen ja Paltamon seurakuntien sekä Kajaanin maaseurakunnan osista itsenäiseksi kirkkoherrakunnaksi Keisarillisen senaatin päätöksen mukaan 11.5.1897. Päätöksessä säädettiin, että kun tuolloin virassa olleet kirkolliset palkansaajat Kajaanin ja Säräisniemen seurakunnissa ovat poistuneet, heidän oikeudenomistajiensa sekä kirkollisviraston leski- ja orpokassan oikeuksia loukkaamatta muodostetaan uusi kolmannen luokan keisarillinen kirkkoherrakunta. Seurakunnan kirkko määrättiin rakennettavaksi Vuolijoen kylään ja siihen tulivat kuulumaan Vuottolahden kyläkunta Kajaanin maaseurakunnasta sekä Saaresmäen ja Vuolijoen kylät Säräisniemen seurakunnasta. Kajaanin ja Säräisniemen papisto oli velvollinen, virkapitäjien poistuttuakin, väliaikaisesti hoitamaan Vuolijoen alueita kunnes uusi seurakunta oli saanut kirkkonsa valmiiksi. Vuolijoen kirkkoherrakunnan alue vapautettiin ottamasta osaa entisten seurakuntien kirkon- ja papinvirkatalojen rakentamiseen ja kunnossa pitämiseen 1.5.1898. Seurakuntaan liitettiin vuonna 1916 Kajaanin maaseurakunnasta Vuottolahden kylä, johon Suomen virallisen tilaston väestönmuutostietojen mukaan kuului tuolloin 578 henkeä. Vuolijoen kunta perustettiin 1915 ja liitettiin Kajaanin kaupunkiin 2007.
Maakirjakylät
Kives, Koutaniemi, Mainua, Manamansalo, Paltaniemi, Saaresmäki, Varisniemi, Vuolijoki, Vuottolahti
Naapuriseurakunnat
Papisto
Seurakunnan tuli hankkia kirkkoherralle vähintään 1/8 manttaalin maatila virkataloksi ja sen tuli olla kuntoon rakennettu ennenkuin virka julistettaisiin haettavaksi. Puuttuneiden tilusetujen korvaukseksi kirkkoherralle oli suoritettava Säräisniemestä tulleista tiloista 864 kiloa heiniä ja 1 3/4 metristä syltä halkoja sekä Kajaanin seurakunnasta tulleilta tiloilta 948 kiloa heiniä kultakin manttaalilta.
Ylimääräiset papit
1907–1909 Juhana Wiljam Hirvonen, väliajan saarnaaja
Arkistot
Vuolijoen seurakunnan rippi- ja historiakirjat alkavat vuodesta 1915.
Seurakunnan pappila paloi 16.6.1922, jolloin tuhoutuivat rippikirjat vuodesta 1910 alkaen, vihittyjen luettelot vuosilta 1908–1922, useita tilikirjoja sekä kirjeenvaihto vuosilta 1908–1922.
Suomen Sukuhistoriallinen yhdistys (SSHY) on digitoinut Vuolijoen seurakunnan kirkonkirjoja. Alle 125 vuotta vanhojen aineistojen tutkiminen vaatii kirjautumisen yhdistyksen jäsensivuille.