Kajaanin linnaa ryhdyttiin rakentamaan vuonna 1604 Ruotsin kuningas Kaarle IX:n määräyksestä. Sen paikka valittiin sotilaallisia näkökohtia silmällä pitäen. I rakennusvaihe päättyi vuonna 1619 ja paikalle jäi pieni varusväki antaen vähän eloa seudulle. Rakennuksia syntyi myös jonkin verran linnan ulkopuolelle Kajaaninjoen molemmille rannoille. Linnan rakentamisen myötä kylvettiin siemen myös tulevan kaupungin synnylle tälle paikalle.

Linnan rakennustöistä vastasi Pohjanmaan käskynhaltija Iisak Behm ja muuraustöitä johti Iisak Rasmusson. Linna joutui 1650 läänityksenä Kreivi Pietari Brahelle Kuningatar Kristiinalta. Brahen määräyksestä aloitettiin II rakennusvaihe, jossa puurakennukset korvattiin kivillä, jotta Kajaani olisi turvattu tulipaloilta. Uusia rakennustöitä ja linnaa johtamaan Brahe määräsi ystävänsä Sakarias Palmbaumin, missä virassa hän pysyi vuoteen 1661. Vuosina 1661-1666 suureen rakennusvaiheeseen tuli linnapäälliköksi Samuel Långh, jolloin linnoitusta ruvettiin vahvistamaan.
Tässä rakennusvaiheessa linna muotoutui 2-kerroksiseksi, kokonaan kivestä tehdyksi vahvaksi linnoitukseksi. Linnan kerrotaan valmistuneen vasta vuonna 1666 Pietari Brahen aikana. Linna ehti seistä luodollaan 50 vuotta, kunnes antautui 24.2.1716 venäläisille viisi viikkoisen piirityksen jälkeen. Vuonna 1716 venäläiset räjäyttivät linnan. 

Avoinna läpi vuoden. Vuonna 2004 Kajaanin linna täytti 400 vuotta.

Sijainti kartalla