Koska Carlislen linna sijaitsee strategisesti tärkeällä paikalla Englannin ja Skotlannin rajalla, ei ole yllättävää, että se on Brittein saarten eniten piiritetyn paikan ennätys. Carlislen rooli merkittävänä hallinnollisena ja sotilaallisena keskuksena alkoi lähes 2000 vuotta sitten, kun siitä tuli roomalainen Luguvalium. Carlislen varhaisin linnoitus, joka oli rakennettu puusta ja puutavarasta, rakennettiin siihen paikkaan, jossa myöhemmin sijaitseva linna nyt on.Carlislen rooli pohjoisen rajan linnoituksena jatkui varhaiskeskiajalla, jolloin se oli osa Rhegedin kuningaskuntaa. Useat tarinat yhdistävät kuningas Arthurin Carlisleen; hänen kerrotaan pitäneen täällä hovia. Kun Northumbrian kuningaskunta oli pohjoisen suurvalta, Carlislesta tuli myös tärkeä uskonnollinen keskus.

Kaiverrus Carlislen linnasta, 1829.

Normanilaisen linnan rakentaminen aloitettiin valloittajan pojan, Englannin Vilhelm II:n aikana, jolloin Cumberlandia pidettiin Skotlantiin kuuluvana alueena. Karkotettuaan skotit pois Vilhelm II vaati aluetta Englannille, ja vuonna 1093 rakennettiin puinen normanilainen motte and bailey -linna aikaisemman roomalaisen linnoituksen paikalle. Vuonna 1122 Henrik I määräsi rakennettavaksi kivisen linnakkeen; kaupunginCarlislen myöhempi historia heijastaa englantilais-skotlantilaisten suhteiden myrskyisyyttä, ja Carlisle ja sen linna vaihtoivat omistajaa monta kertaa seuraavien 700 vuoden aikana. Kaupunki oli myös molempien maiden hallitsijoiden voittojen ja tragedioiden näyttämö. Skotlannin Daavid I otti Carlislen jälleen skottien haltuun Henrik I:n kuoleman jälkeen. Hänen kerrotaan rakentaneen "aLinna oli jälleen englantilaisten hallussa Henrik II:n (1154-1189) aikana, kun hän asetti Cumberlandin sheriffin Robert de Vaux'n linnanhoitajaksi. Linnanhoitajilla ja myöhemmin vartijoilla oli tärkeä rooli järjestyksen ylläpitämisessä englantilais-skotlantilaisella rajalla.

Linna kehittyi entisestään, kun Carlislesta tuli Edward I:n päämaja hänen ensimmäisen skotlantilaiskampanjansa aikana vuonna 1296. Seuraavien kolmen vuosisadan aikana Carlislea piiritettiin seitsemän kertaa, muun muassa Robert Bruce piiritti sitä pitkään Bannockburnin jälkeen. Lopulta linna oli tiukasti englantilaisten hallussa, ja siitä tuli West Marchin vartijoiden päämaja. Kaupungin massiivisia puolustuksia rakennettiin lisää.Se rakennettiin Henrik VIII:n aikana, jolloin hänen insinöörinsä Stefan von Haschenperg suunnitteli myös Henrikille tyypillisen Citadelin. Maria Skotlannin kuningatar vangittiin Warden's Toweriin vuonna 1567. 1500-luvun lopulla pahamaineinen rajakorppari Kinmont Willie Armstrong pelastettiin rohkeasti Carlislen linnasta, joka oli tuolloin myös vankila. Vielä kruununliiton jälkeenkin vuonna 1603 Carlislen linna säilyi edelleen.säilytti sotilaalliset perinteensä, sillä se oli kuninkaan hallussa sisällissodan aikana, kunnes se joutui antautumaan parlamentin piirityksen jälkeen, kun asukkaat näännyttivät sen nälkäänsä ja alistuivat. Myös jakobiittijoukot valtasivat linnan ja pitivät sitä hallussaan vuonna 1745. Nykyään tämän voimakkaan pohjoisen linnoituksen sotilaalliset perinteet jatkuvat Cumbrian sotilasmuseon kautta.