Kokkolanlahden alue kuului alkuaan Pietarsaaren eli Pedersören emäseurakuntaan, josta se erotettiin omaksi pitäjäkseen 1467. Mainitaan itsenäisenä kirkkoherrakuntana ainakin jo 1541. Seurakunnan vanha ruotsinkielinen nimi Karleby muutettiin Uudenkaarlepyyn perustamisen myötä Gamla Karlebyksi 1607. Seurakunnan alueelle perustettiin Kokkolan kaupunki 1620 ja kaupunki erotettiin itsenäiseksi kirkkoherrakunnaksi 1918. Kokkolan maalaiskunnan nimi muutettiin Kaarlelaksi 1927 ja Kaarlelan kunta liitettiin Kokkolan kaupunkiin 1977.
Seurakuntaan kuuluneista Lohtaja perustettiin anneksiseurakunnaksi 1467 ja erotettiin itsenäiseksi kirkkoherrakunnaksi 1575. Kälviä erotettiin 1639. Yliveteli perustettiin kappeliksi ja erotettiin 1860, jolloin sai nimen Veteli. Alaveteli perustettiin kappeliksi 1752 ja erotettiin 1894. Perho perustettiin saarnahuonekunnaksi 1780 ja siirrettiin kuulumaan Veteliin 1865. Halsua perustettiin saarnahuonekunnaksi 1826, muodostettiin kappeliksi 1856 ja siirrettiin kuuluvaksi perustettuun Vetelin kirkkoherrakuntaan 1860. Kaustinen perustettiin kappeliksi 1776 ja erotettiin 1866.
Muut nimet
Kaarlela, Karleby landsförsamling, Kokkolan maaseurakunta
Kylät
Isokylä, Kallinen, Kaustari, Kirilahti, Knivsund, Korplahti, Kvikant, Långö, Linnusperä, Närvilä, Oivu, Palo, Rödsö, Sokoja, Vitsari
Naapuriseurakunnat
Papisto
Kirkkoherran virkataloon sanotaan kuuluneen vanhemmista joista Mottis-niminen suo, josta kihlakunnanoikeuden tuomio 12.7.1852 ja kuninkaallisen Turun hovioikeuden päätös 18.4.1661. Kirkkoherran vastikejyvistä kuninkaan päätös 11.9.1734. Papiston palkasta tehtiin sopimus 10.1.1735. Kappalaisen palkasta kuninkaallisen kamarikollegion päätös 16.12.1776. Maaseurakunnan anomukseen toisen kappalaisen palkkaamiseksi kaupunkia varten antoi kuningas epäävän vastauksen 30.11.1802. Seurakunnassa oli pitäjänapulaisia ainakin 1680-luvulta alkaen, kunnes virka lakkautettiin keisarin päätöksellä 23.10.1852. Pitäjänapulainen toimi myös pedagogina vuoteen 1805. Seurakunnan molemmat kappalaisen virat yhdistettiin keisarin käskykirjeellä 24.1.1861, jolloin ensimmäisen kappalaisen virkatalo määrättiin vuokrattavaksi tulevaa kansakoulua varten sillä ehdolla, että jos seurakuntaan asetettaisiin tulevaisuudessa toinen kappalaisen virka, virkatalo tulisi tämän kappalaisen nautittavaksi. Papiston palkasta keisarin päätöksissä 8.6.1855 ja 7.11.1861.
Kirkkoherrat
? Nicolaus Galle
1554 Karl
1563–1564 Erich
1566–1568 Håkan Laurentii
1569–1580 Olaus Nicolai
1582–1620 Carolus Erici Sursill
1622–1637 Jaakko Matthiæ Skepperus (Gammal)
1637–1654 Eerik Nicolai Galle
1655–1672 Eerik Matthiæ Falander
1673–1693 Isaacus Erici Falander
1693–1694 Andreas Petraeus
1694–1702 Jaakko Westzynthius
1703–1720 Jaakko Falander
1720–1735 Antti Kiemmer
1735–1743 Karl Gustaf Werander
1746–1766 Jakob Chydenius
1767–1769 Johan Haartman
1770–1803 Anders Chydenius
1806–1814 Fredrik Stenhagen
1817–1837 Karl Johan Nordling
1840–1854 Simon Vilhelm Appelgren
1857–1868 Abraham Vilhelm Chydenius
1872–1881 Ture Birger Vegelius
1883–1886 Johan Holmberg
1890–1894 Karl August Finelius
1896–1917 Edvard Johansson
1919–1930 Fredrik William Neunstedt
1930–1935 Paul Krokfors, vt. kirkkoherra
1935–1964 Tor Krook
1. kappalaiset
–1569 Olaus Nicolai
1593–1607 Paulus Dionysii
1605–1607 Carolus Jacobi
1616–1622 Jakob Matthiæ Skepperus (Gammal)
1622–1641 Mathias Ruuth
1628–1639 Johannes Simonis Nurka
1648–1667 Mathias Johannis Grandelius
1648–1651 Jaakko Georgii Ingelmontanus
1651–1659 Josef Johannis Wasaeus
1660–1665 Juhana Matthiæ Tastenius (Tast)
1666–1673 Isak Falander
1673–1680 Erik Olai Carlenius
1680–1687 Erik Essevius
1687–1690 Kristoffer Olai Carlenius
1691–1697 Ernst Grandell
1698–1707 Olavi Wendelius
1708–1720 Erik Jacobus Falander
1708–1722 Henrik Engmark
1721–1728 Johan Röring (Roering)
1729–1739 Mathias Pazelius
1739–1751 Andreas Gadolin
1752–1762 Nils Johannis Snellman
1763–1810 Johan Snellman
1797–1810 Fredrik Juvelius
1812–1819 Jakob Aulin
1822–1828 Anders Gustaf Ekholm
1831–1857 Abraham Vilhelm Chydenius
1890–1903 Fredrik William Nejnstedt
1903–1910 Olof Werner Bengs
1910–1922 August Albinus Westerlund
1922–1934 Tor Krook
1935–1965 Paul Krokfors
2. kappalaiset
1614–1615 Nicolaus Matthiæ Ryngius (Ryngen)
1616–1622 Mathias Skepperus
1628 Henrik Merijervus (Ristrenius)
1639–1660 Martinus Michaelis Peitzius
1661–1675 Caspar Marcii Neostadius
1679–1687 Jaakko Ericii Falander
1687–1693 Daniel Grandelius
1695–1696 Andreas Johannis Hamnius
1697–1714 Jaakko Isaaci Falander
1724–1738 Henrik Röring
1738–1745 Erik Kuhlberg
1745–1758 Martin Gabrielis Peitzius
1759–1780 Mathias Pazelius
1781–1801 Fredrik Stenhagen
1803–1815 Fredrik Jurvelius
1817–1822 Johan Stenfors
1826–1850 Jonas Gabriel Taxell
1851–1890 Karl August Finelius
Pitäjänapulaiset
1635–1660 Carolus Hordelius
1660–1661 Kasper Neostadius
1671–1680 Jacobus Laxenius
1681–1686 Gustavus Ulstadius
1686–1687 Daniel Grandelius
1687–1691 Ernst Grandelius
1691–1698 Olavi Wendelius
1698–1711 Kustaa Snabb
1711–1715 Gustaf Momma
1711–1722 Henrik Röring
1722–1724 Georg Tengström
1726–1735 Johan Forsman
1735–1736 Thomas Arenius
1736–1737 Henrik Röring
1737–1738 Erik Kuhlberg
1738–1752 Nils Snellman
1753–1767 Johan Tengström
1769–1779 Johan Reinholm
1779–1781 Fredrik Stenhagen
1782–1783 Jakob Simelius
1784–1791 Johan Tengström
1792–1808 Nils Johan Ahlbäck,
1809–1812 Jakob Aulin
1813–1835 Fredrik Stenhagen
1837–1842 Johan Ahlholm
1842–1846 Alexander Jakob Gummerus
1849–1851 Anders Gustaf Östberg, virka lakkautettiin 1852
Armovuodensaarnaajat ja apupapit
1735–1736 Petter Niklas Mathesius, kirkkoherran viran armovuodensaarnaaja
1741–1745 Samuel Simalin, kappalaisen apulainen
1753– Lars Gallenius, kappalaisen apulainen
1754– Jakob Chydenius, kirkkoherran apulainen
1754–1755 Johan Uhlman, kappalaisen apulainen
1757–1759 Matthias Pazelius, kappalaisen apulainen
1760–1762 Johan Forsman, kappalaisen apulainen, kappalaisen viran armovuodensaarnaaja
1774–1779 Fredrik Stenhagen, kappalaisen apulainen
1781–1783 Johan Tengström, kirkkoherran apulainen
1784–1787 Gabriel Borg, kirkkoherran apulainen
1788–1792 Johan Stenbäck, kirkkoherran apulainen
1794–1805 Karl Johan Nordling, kirkkoherran apulainen
1813–1817 Lars Schalin
1820–1826 Johan Tamlander
1831–1842 Alexander Jakob Gummerus
1851–1856 Viktor Vilhelm Krank
1868–1871 August Vilhelm Bergman
1887–1890 Fredrik William Nejnstedt
Ylimääräiset papit
1794–1805 Karl Johan Nordling, kirkkoherran apulainen
1809–1813 Fredrik Stenhagen, kirkkoherran apulainen
1817–1831 Abraham Vilhelm Chydenius, kirkkoherran apulainen
1828–1829 Abraham Neuman, kappalaisen apulainen
1829–1831 Leonard Per Häggström, vt kappalainen
1829–1831 Karl Peter Arenius, pitäjänapulaisen apulainen
1830–1831 Robert Örnström, kirkkoherran apulainen
1843–1849 Anders Gustaf Östberg, kirkkoherran apulainen
1846–1858 Isak Otto Appelberg, välisaarnaaja, kirkkoherran apulainen
1848–1850 Frans August Hällberg, kirkkoherran apulainen
1853 Alfred Kihlman, kirkkoherran apulainen
1853–1854 Karl Johan Ahonius, kirkkoherran apulainen
1857–1862 Jakob Schroderus, välisaarnaaja, kappalaisen sijainen
1858 Anders Abraham Favorin, vt. pitäjänapulainen
1858–1862 Fredrik Alexander Sterenius, vt. pitäjänapulainen
1881–1883 Gustaf Durchman, vt. kirkkoherra
1884–1885 Ludvig Joakim Maximilian Lagerbohm, kirkkoherran apulainen
1893 Frans Adolf Rudanko, kirkkoherran apulainen
1893–1895 Gustaf Gideon Castren, kirkkoherran apulainen
1895–1896 August Hjalmar Tranchant, välisaarnaaja
1899–1910 Frans Oskar Lampola, kirkkoherran apulainen
1917–1922 Karl Mikael Melmberg, vt. kirkkoherra
Arkisto
Kokkolan eli Kaarlelan seurakunnan rippikirjat alkavat vuodesta 1724, tilikirjat vuodesta 1655 ja historiakirjat vuodesta 1654. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Vaasassa ja aineistokokonaisuus kattaa vuodet 1620–1875.
Kansallisarkisto on digitoinut Kokkolan 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.