Tras la conquista musulmana, entre los siglos VIII y IX, se construye un conjunto amurallado estructurado en dos espacios: un amplio recinto o alcázar en la cumbre y la alcazaba propiamente dicha, en la ladera norte, que aprovecha los restos de la muralla romana. La alcazaba fue un gran recinto de carácter defensivo-residencial, en el que se ha documentado un edificio rectangular con patio porticado, que pudo ser la residencia de los primeros gobernadores de la ciudad en época Emiral-Califal. El traslado de la capital de la Kura a Ŷayyān en el siglo IX conllevó un fuerte desarrollo de la ciudad, restaurándose las estructuras de fortificación existentes, a la vez que se levantan nuevos lienzos y torres. 

La cambiante situación política en al-Andalus entre los siglos XI y XIII provocó una intensa reforma de las murallas, que culminaron con la transformación del alcázar de la cumbre en una gran y compleja fortaleza. Se configura así un gran conjunto fortificado estructurado en dos recintos: en el extremo oeste se erige un primer recinto en tapial de argamasa, de planta irregular, conocido como Castillo de Abrehuí; al este se dispone el cercado principal, conocido como Alcázar Viejo, al que se accedía por una puerta protegida por dos torres paralelas. Al mismo tiempo, se construye un nuevo espacio político-administrativo en la zona oriental del Alcázar Viejo, un palacio del que las investigaciones arqueológicas han logrado recuperar diversos vestigios, así como determinar cómo fue su distribución, diferenciando las estancias inferiores y las superiores, en las que se emplazó el palacio, engalanado con una profusa y lujosa decoración de yeserías y zócalos ornamentados que cubrían sus muros (parte de las cuales se exhiben en el Museo Provincial de Jaén).

La conquista de Jaén en 1246 determinó una importante alteración de la trama urbana de la ciudad, y de sus estructuras defensivas. Los muros y torres de tapial se revisten con forros de mampostería. La antigua fortificación islámica de la cumbre mantuvo su antiguo trazado, excepto por la edificación, entre los siglos XIII y XIV-XV, de una nueva fortaleza que ocuparía su extremo este, denominada Alcázar Nuevo. Su perímetro externo está delimitado por un recinto amurallado que incorpora 6 torres, edificadas en mampostería. Las torres son de planta cuadrada, excepto la más oriental (torre de la Vela o de la Guardia) que tiene forma pentagonal en proa, al embutir en su interior una antigua torre islámica. Todas ellas están comunicadas entre sí por adarves almenados. La del Homenaje se divide en tres estancias. La primera, cubierta con cuatro bóvedas de ladrillo que confluyen en un único pilar central y carece de iluminación exterior, tendría una función de almacenaje. La segunda se cubre mediante bóveda esférica de ladrillo sostenida en cada esquina por una columna de piedra. El tercer piso tiene bóveda poligonal de ladrillo y tendría una función residencial. En las excavaciones arqueológicas también aparecieron yesos decorados, fechados entre los siglos XIV y XV, que revestirían los paramentos de la capilla de Santa Catalina, quizá introducidos tras las reformas que en ella realizó el Condestable D. Miguel Lucas de Iranzo. 

Al este de la puerta del castillo, en el lado norte del recinto, se suceden dos torres albarranas, la más occidental, maciza en la parte inferior y con una dependencia en la superior, alberga la Capilla de Santa Catalina, patrona de la ciudad. La oriental, muy restaurada, tendría una función militar, careciendo de dependencia, por lo que conformaría un cubo macizo coronado por una azotea almenada. En el lateral sur se abre un portillo o poterna junto a la Torre de las Troneras, que alberga unas letrinas. Intramuros se disponían dependencias y elementos para el funcionamiento interno del castillo: aljibes, un área de molienda y otras estancias. 

En el tercer cuarto del siglo XV, durante la guerra civil que se desarrolló durante el reinado de Enrique IV, el Condestable Miguel Lucas de Iranzo refuerza nuevamente las defensas de la ciudad, dotando a las murallas de antemuro y foso, demoliendo parte de los adarves y cegando algunas torres de la muralla Norte, acentuando la impugnabilidad de la ciudad frente a los enemigos el monarca castellano.

Entre los siglos XVI y XVIII se producen remodelaciones en algunas dependencias del Alcázar Nuevo, que cambian de función, se construyen otras nuevas y se ciega la poterna del sector sur.

A principios del siglo XIX, la guerra de independencia provocó cambios importantes en la estructura de esta fortaleza, a pesar de lo cual se mantiene la fisonomía exterior de la fortificación medieval. Las remodelaciones, que ocasionaron la destrucción de estructuras y dependencias, comprenden la reparación de murallas, la anulación de portillos, la construcción de nuevas estructuras defensivas, y el levantamiento de grandes edificios para diversos usos, caballerizas, cuarteles, hospital, puestos de guardia, polvorines, etc., de los que apenas quedan restos en la actualidad, como consecuencia de la edificación del Parador de Turismo entre 1963 - 1978 y la ejecución de diversas obras de restauración realizadas en los años 80. 

El cerro de Santa Catalina ha estado poblado desde la Edad del Cobre, aunque las estructuras más antiguas documentadas pertenecen a un oppidum ibérico, fechado en torno al siglo IX a.n.e., e identificado como Oringis. Entre los siglos II y I a.n.e. los romanos lo transformarán en un nuevo asentamiento fortificado de planta poligonal. La constitución del Municipio Flavio Aurgitano, a fines del siglo I d.n.e., provocó la rápida urbanización del espacio que actualmente ocupa el barrio de La Magdalena, delimitado por un recinto amurallado.

El abandono y expolio de edificios que formaban el foro romano o la presencia de tumbas aisladas y basureros muestran la progresiva transformación de la ciudad bajo imperial entre los siglos III y IV de nuestra era, mutación que continuaría en época visigoda. 

Tras la conquista islámica, las primeras noticias sobre la actual Jaén (Ŷayyān) datan de mediados del s. IX cuando el emir omeya Abd al-Rahman II convierte la ciudad en nueva capital de la Cora, erigiéndose la alcazaba, germen del actual castillo de Santa Catalina, así como parte de las murallas que lo enlazaban con la ciudad. En estos momentos se construyen los primeros palacios que, acabarán conformando el alcázar situado en la medina. 

A partir del s. XI, y especialmente durante el periodo almohade (1169-1246), la ciudad fue expandiéndose hacia el sur. Se produjo también la reforma y ampliación del alcázar omeya y taifa ubicado en la propia medina, dotado de jardines y palacios, lujosamente decorados, mientras que en el castillo se crea una zona residencial-administrativa. 

Tras la conquista castellana en 1246 la configuración urbana de Jaén no debió de experimentar grandes cambios hasta los siglos XIV-XV. Fernando III procedió a repoblarla y repartirla, quedando en manos del Concejo y convirtiéndose en sede episcopal. La inestabilidad del territorio hasta la conquista de Granada en 1492, y las luchas nobiliarias durante el reinado de Enrique IV provocaron que las reparaciones de los elementos defensivos fueran constantes: la muralla almohade se reviste de mampostería, mientras comienza la construcción de un Alcázar Nuevo en el extremo oriental del Cerro de Santa Catalina. Por su parte, el alcázar almohade emplazado en el epicentro de la ciudad estuvo en manos de la corona castellana hasta que en 1382 se convirtió en el convento de Santo Domingo.

A principios del siglo XIX, durante la invasión de España por las tropas napoleónicas, Jaén y sus defensas volvieron a tener un papel destacado, manteniendo el control de la ciudad ante el ataque y saqueo de 1808, antes de pasar a manos de los franceses en 1810. La inestabilidad imperante entre 1808 y 1814 conllevó importantes remodelaciones en las fortificaciones del cerro, convirtiéndolas en un gran acuartelamiento desde el que ejercer el control de la mayor parte de la provincia y de los caminos hacia Granada y Córdoba. Tras el final de la guerra de independencia, las estructuras defensivas del cerro y de la ciudad se mantuvieron en pie, aunque sufriendo un progresivo proceso de deterioro, el cual se acentuó más aún a lo largo del siglo XX, a finales del cual se llevaron a cabo diversas obras de restauración.

LEYENDAS

Leyenda de la aparición de Santa Catalina. Cuenta la leyenda que durante el sitio de Jaén al rey Fernando III se le apareció en sueños Santa Catalina de Alejandría que le mostró las llaves de Jaén, tomándolo como un presagio. Al día siguiente, los musulmanes hicieron entrega de la fortaleza a las tropas cristianas y en agradecimiento Fernando III nombró a Santa Catalina patrona de la ciudad, poniendo su nombre a la fortaleza recién conquistada
La cámara de las estatuas. En el castillo Viejo había un recinto secreto con una puerta fuertemente cerrada, a la que cada rey añadía una nueva cerradura. Cuando ya contaba con 24, un usurpador que se apoderó del trono, se negó a continuar la tradición, ordenando abrir la estancia. En su interior encontró un altorrelieve, de metal y madera, con temibles guerreros árabes a caballo y una inscripción que profetizaba "Si alguna mano abre la puerta de este castillo, los guerreros de carne que se parecen a los guerreros de metal se adueñarán del reino". Antes de que acabara el año, Tarik, tomó la fortaleza.

Leyenda de la cruz del castillo. La leyenda dice que cuando el rey Fernando III entró en la fortaleza de Jaén, tras conquistar a los musulmanes, uno de sus capitanes hincó una espada, como señal de triunfo, en un promontorio rocoso en el extremo sur del cerro, desde el que se dominan las tierras de Jaén.

La forma que creaban la hoja y el travesaño del arma semejaban una cruz cristiana. El rey Fernando III, fascinado, decidió que siempre hubiese una gran cruz en ese mismo punto para recordar la conquista de las tropas cristianas. Una leyenda que terminó convirtiéndose en tradición.