Ruotsin kuningas Kaarle IX käski rakentaa Kajaaninjoen saareen linnan. Sitä rakennettiin vuosina 1604–1619, mutta Kajaanin perustaja Pietari Brahe uudistutti linnaa 1660-luvulla. Silloin linnan sisäpihalla olevat puutalot korvattiin kivitaloilla.
Vuonna 1716 Suuren Pohjan sodan aikana venäläiset valtasivat linnan. Kajaanin linnan 50 puolustajaa eivät lopulta pystyneet vastustamaan 4 000 venäläissotilasta vaan antautuivat pitkän piirityksen jälkeen. Taistelunäytöksessä väkeä on vähemmän, esityksessä on noin 70 historianharrastajaa, joista osa on ollut mukana vastaavissa näytöksissä ympäri Eurooppaa.
Antautumisen jälkeen venäläiset räjäyttivät linnan. Muurit romahtivat ja niiden päällä olleet maavallit täyttivät linnanrauniot. Nykyisin linnan raunioiden päällä kulkee maantiesilta, joka rakennettiin vuonna 1936.
Linnaa ei ole koskaan korjattu lukuisista suunnitelmista huolimatta, vaikka sitä on suunniteltu 1700-luvulta lähtien. Tänä päivänä rauniolinna on suosittu käyntikohde.