Seudun asutus sai alkunsa, kun Kustaa Vaasa 1550 kehotti maansa viranomaisia järjestämään alueelle uudisasukkaita, jotka saivat muutaman vuoden verovapauden. Venäläisten hyökkäysten varalta uudisasutuksen turvaksi rakennettiin myöhemmän Kajaanin seudulle kuninkaankartano, josta käytettiin nimitystä Oulun Palte. Asutus kuului aluksi Limingan pitäjään, mutta jo 1559 asukkaita varten oli oma pappi. Uudesta pitäjästä käytettiin alkuun nimitystä Oulujärven eli Oulun erämaan seurakunta ja myöhemmin nimeä Paltamo. Kajaanin linnan rakentaminen aloitettiin 1604 PohjanmaankäskynhaltijanIisak Behmin johdolla. Toisinaan uutta seurakuntaa nimitettiin Kajaanin linnan mukaan Kajaanin linnanpitäjäksi. Vuonna 1716 ylivoimainen venäläinen sotajoukko pakotti linnoituksen antautumaan, jonka jälkeen he tuhosivat linnan räjäyttämällä.[3] Samalla myös Kajaanin lääni siirtyi historiaan.