Kajaanin linna perustettiin kuningas Kaarlen käskykirjeellä 5.5.1607 ja se valmistui 1666. Kajaanin vapaaherrakunta, johon kuuluivat Paltamo, Sotkamo, Kuopio, Iisalmi, Salo ja Pielinen, annettiin läänityksenä kreivi Per Brahelle 1650. Linnan ympärille kasvoi kylä, jolle Brahe antoi kaupungin oikeudet 6.3.1651. Kajaanin ensimmäinen kirkko rakennettiin 1652. Sai vakituisen linnansaarnaajan 1613, jonka virka muutettiin kirkkoherran viraksi 1651 ja Kajaani muodostui näin omaksi kirkkoherrakunnaksi ollen kirkkoherran ja kappalaisen hoidettavana ainakin 1654-1721. Erillinen linnansaarnaaja asetettiin uudelleen ja seurakunta muutettiin luonteeltaan konstistoriaaliseksi kuninkaallisella käskykirjeellä 20.11.1781. Kirkkoherran virka lakkautettiin ja seurakunta liitettiin anneksina Paltamoon kuninkaallisella käskykirjeellä 23.1.1786, ja seurakuntaa hoito oma kappalainen. Erotettiin Paltamosta itsenäiseksi kirkkoherrakunnaksi keisarillisen senaatin päätöksellä 19.5.1897, jossa myös määrättiin kirkkoherra palkkaaman itselleen apulainen, ja ero toteutui jakamattomana Kajaanin maa- ja kaupunkiseurakuntana 1925. Kajaanista liitettiin osia tuolloin perustettiin Vuolijoen kirkkoherrakuntaan. Kajaanin kunta perustetiin 1870 ja maalaiskunta liitettiin Kajaanin kaupunkiin 1977.
Isonvihan aikana seurakunnan kirkko ryöstettiin ja poltettiin 13.12.1712. Venäläiset pitkällisen saartamisen jälkeen hävittivät linnan ja polttivat kaupungin sekä sen vanhan kreivi Brahen rakennuttaman kirkon. Uuden kirkon rakentamista varten myönnettiin 89 500 markan valtionlaina ja se vihittiin 29.11.1896. Kirkossa oli tulipalonalku 31.1.1942, joka saatiin tukahdutettua.
Muut nimet
Kajana
Kylät
Jormua, Koutaniemi, Kuluntalahti, Lahnasjärvi, Lehtovaara, Linnantaus, Mainua, Murtomäki
Naapuriseurakunnat
Papisto
Linnansaarnaajan palkka oli aluksi 30 taalaria hopeassa ja kuusi tynnyriä, jotka vahvistettiin kuninkaallisella käskykirjeellä 10.7.1680. Paltamon kirkkoherralle maksettavista kymmenynistä kaupungin lahjoitusmaasta annettiin kuninkaallinen käskykirje 23.1786 ja keisarillisen senaatin päätös 25.10.1820. Kajaanin kappalaisen palkasta annettiin keisarillisen senaatin päätös 22.11.1867. Äänten lukemisesta papinvaalissa seurakunnassa annettiin keisarillinen käskykirje 20.10.1830. Kappalaisen 50 ruplan palkasta vankien hoidosta säädettiin keisarillisella käskykirjeellä 16.3.1860. Seurakunnasta Paltamon kirkkoherralle menevistä maksuista antoi keisarillinen senaatti päätöksen 12.4.1894.
Kirkkoherrat
1655–1679 Jacobus Petri Teudscovius (Tysk)
1680–1704 Johan Antilius (Arctelius)
1705–1713 Gabriel Erici Cajanus
1714–1719 Zacharias Forbus
1721–1727 Anders Hildén
1728–1732 Isak Rothovius
1733–1746 Lars Henrik Backman
1747–1763 Johan Frosterus
1764–1781 Olof Westzynthius
1782–1786 Gabriel Mathias Lescelius
Kappalaiset ja pedagogit
1654–1660 Thomas Henrici Uhlander
–1670 Andreas Antilius
–1680 Johannes Antilius
–1703 Samuel Petrelius
1707–1721 Andreas Hildén
1721–1786 virka lakkautettuna
1786 Sigfrid Carlenius, vt. kappalainen
1787–1796 Johan Wichman
1796–1807 Simon Johan Castrén
1807–1813 Anders Wichmann
1814–1844 Johan Reinhold Appelgren
1845–1863 Gustaf Fredrik Högman
1865–1877 Frans Napoleon Salonius
1881–1893 Johannes Zakarias Hartman
1894–1925 Johannes Väyrynen
Apupapit ja armovuodensaarnaajat
1813–1824 Johan Gustaf Costiander
1817–1822 Carl Saxa
1819– Adolph Forbus
1879–1880 Fredrik Mielonen
1878–1881 Oskar Hjalmar Valdemar Fabritius
Linnansaarnaajat
–1613 Matthias Johannis
1613– Thomas Nicolai
Ylimääräiset papit
1746–1747 Johan Frosterus, vt. kirkkoherra
1780–1781 Petter Junnelius, vt. kirkkoherra
1786–1787 Johan Wichman, vt. kirkkoherra
1810–1814 Johan Reinhold Appelgren, kappalaisen sijainen, välisaarnaaja
1837–1838 Johan Jakob Ingman, kappalaisen apulainen
1839–1841 August Kranck, kappalaisen apulainen
1841–1845 Karl Jakob Keckman, kappalaisen apulainen, välisaarnaaja
1863–1864 Olof Alfred Vallin, välisaarnaaja
1864–1865 Gustaf Leonard Meklin, välisaarnaaja
1875–1878 Fredrik Mielonen, kappalaisen sijainen
1888–1889 Frans Petter Vuornos, kappalaisen apulainen
1893–1894 Kaarlo Aukusti Pohjola, välisaarnaaja
Arkisto
Kajaanin seurakunnan rippikirjat alkavat vuodesta 1729, tilikirjat vuodesta 1755 ja historiakirjat vuodesta 1757. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Oulussa ja aineistokokonaisuus kattaa vuodet 1729–1900.
Kansallisarkisto on digitoinut Kajaanin 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.