Helluntaiherätyksen työ Muhoksella on alkanut 1930-luvulla. Uskovat kuuluivat silloin rukouspiirinä Oulun Helluntaiseurakuntaan. Omaa rukoushuonetta alettiin suunnitella Muhokselle 1980-luvun alkuvuosina. Rukoushuoneen rakentaminen aloitettiin keväällä 1985 ja se vihittiin käyttöön 6.7.1986.

Muhoksen helluntaiseurakunnan rukoushuoneen suunnitteli Arkkitehti Martti Torvikoski Oulusta. Rakennus rakennettiin yli 90 %:sti talkootyönä. Merkittävänä apuna hankkeen rahoituksessa oli monet lahjoitukset. Mm. puutavara saatiin lähes kokonaan lahjoituksina paikallisilta metsän omistajilta!

Rakennuksen pinta-ala on 440 m2. Kokoussalissa on istumapaikat n. 170 hengelle. Lisäksi on ruokailu- ja kerhotilat, toimistotilat sekä 52 m2 asunto. Itsenäisen seurakunnan aika alkoi vuonna 1991, jolloin sekä Oulun emäseurakunnassa että Muhoksella nähtiin että on aika järjestäytyä omaksi seurakunnaksi.

Seurakunnan perustamisjuhlia vietettiin 29.9.1991. Seurakunnassa on jäseniä n. 40. Vaalan, Utajärven ja Kestilän alueella asuvat seurakuntalaiset järjestäytyivät omaksi Vaalan helluntaiseurakunnaksi 18.3.2001.

Keväällä 2006 rukoushuoneella sattui laaja vesivahinko, jonka korjaustyöt kestivät koko loppuvuoden. Remontoitujen tilojen käyttöönottojuhlaa vietettiin 7.1.2007.