Kalajoen varressa kristillistä asutusta oli jo 1200-luvulla. Ensimmäiset maininnat Kalajoen seurakunnasta löytyvät vuodelta 1525, missä kerrotaan, että Kalajoen Tyngän kylälle oli rakennettu kappelikirkko. Seurakunta käsitti tuolloin koko Kalajokilaakson aina Haapajärveä ja Reisjärveä myöten. Laaja emäseurakunta jakaantui 1800-luvulla osiin, kun kappeliseurakunnat itsenäistyivät yksi toisensa jälkeen, ensimmäisenä Haapajärvi v. 1838 ja viimeisenä Rautio v. 1921.

Emäseurakunnan kirkko ei ollut kovin pitkään Tyngällä, vaan seuraava rakennettiin lähemmäksi jokisuuta Luutaojan varteen ja kolmas kirkko nykyisen terveyskeskuksen kohdalle jokitörmälle. Vieressä virtaava joki kulutti maata kirkon alta ja se alkoi kallistua jokeen päin. Tästä syystä kirkko jouduttiin purkamaan v. 1636 ja neljännestä kirkosta alkaen kirkot ovat sijainneet nykyisellä paikalla Junnikkalan mäellä. Neljännen kirkon kohtalo oli Ison vihan keskellä lahota ja ränsistyä ja siksi oli rakennettava viides kirkko, joka valmistui v. 1780. Sekin tuhoutui sodan seurauksena, kun Ruotsi-Suomen joukot polttivat kirkon ja tapulin v. 1808 perääntyessään Kalajoelta.

Kuudes kirkko valmistui v. 1815 ja ehti toimia Herran huoneena aina vuoteen 1869, jolloin salaman sytyttämä se tuhoutui perustuksia myöten. Tämän palon jälkeen kalajokiset päättivät rakentaa kirkkonsa tiilestä. Näin valmistui v. 1879 komea punatiilikirkko, joka sekin joutui tulen tuhoamaksi puuosien osalta helmikuussa 1930. Jykevien seinien sisään rakennettiin nykyinen kirkko, joka otettiin käyttöön v. 1931. Kirkko on sen jälkeen peruskorjattu ja maalattu v. 1979 kirkon satavuotisjuhlia varten sekä v. 1999, jolloin kirkon etuosaan saatiin uudet urut ja alttarialue korjattiin siten, että se voi paremmin palvella uudistuneen jumalanpalveluksen toteuttamista.

Jokelan pappila. Kuva: Eveliina PylväsMuita toimitiloja seurakunnalla on seurakuntakoti (1970), Vuorenkallion kappeli (1982) ja historiallinen Jokelan (1802) pappila, jossa on seurakunnan toimistotilat. Viime vuosikymmenen entisöintien ja korjausten ansiosta ulkonaiset puitteet monipuoliselle seurakunnalliselle toiminnalle ovat hyvät.

1800-luvulta alkaen on herätysliikkeillä ollut merkittävä sija seurakunnallisessa elämässä. Siitä muistuttavat yhä Kalajoella pidetyt ”herännäiskäräjät” 1838-39, joissa heränneisiin kuuluvia pappeja ja maallikoita tuomittiin luvattomien seurojen pidosta ja varojen keräämisestä pakanalähetystyölle. Tuomittujen joukossa olivat mm. Paavo Ruotsalainen ja Niilo Kustaa Malmberg. Lestadiolaisuuden vaikutus ajoittuu varsinaisesti 1900-luvulle, jolloin muodostuivat Kalajoelle eri lestadiolaisuuden haarat: vanhoillislestadiolaisuus, uusheräys ja rauhansanalaisuus. Herätysliikkeiden välillä ei ole ollut suurempia ristiriitoja ja nykyisin ne rikastuttavat seurakunnan elämää omalla paikallaan hyvässä yhteishengessä seurakunnan muun toiminnan kanssa.

 
Luettelo Kalajoen kirkkoherroista 

1543 - 1548 ja 1551 - 1555 Mikael Tavastius
1558 - 1577  Gregorius Keiraskius
1578 - 1588     Dionysius Tavastensis
1590 - 1592  Sigfrid Balk
1592 - 1610 Ljungo Tuomaanpoika
1610 - 1647   
Pietari Arctophilacius
(lisäksi kappalaisena 11v.)
1648 - 1685
Josef Mathesius vanh.
(lisäksi kappalaisena 18 v. eli yht. 55v.)
1686 - 1689 Josef Mathesius nuor.
1689 - 1697 Kaarle Kalling
1697 - 1709 Abraham Falander
1709 - 1715   Erik Wallenius
1716 - 1722  Pietari Calamnius
1722 - 1730   Olaus Cygnell
1731 - 1739  Erik Falander
1739 - 1778 Johannes Salmenius vanh.
1780 - 1796   Johannes Salmenius nuor.
1799 - 1806  Jacob Simelius
1809 - 1838  Johan Frosterus
1839 - 1861 Abraham Montin
1863 - 1866 Herman Magnus Inberg
1869 - 1879  Berndt Enoch Ingman
1881 - 1899   Kaarlo Aadam Ottelin
1901 - 1919  Jaakko Pohjonen
1920 - 1927  Juho Anton Heilala
1929 - 1940  Juho Arvi Metsovaara
1940 - 1968
Vilho Heikki Kivioja
(lisäksi kappalaisena 1923-1940)
1968 - 1992 Kauko Juhani Kajava
1992 - 2014
Rauli Heikki Junttila
(lisäksi kappalaisena 1984-1992)
2014 - Kari Lauri