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.

El castillo de Santa Catalina es un símbolo para los giennenses y Juan Eslava Galán se hace eco y lo introduce continuamente en sus obras, como hace en Los Templarios y la Mesa de Salomón.

(…) Durante mis estancias en Jaén había subido varias veces al castillo de Santa Catalina. Después de atisbar los secretos de su constructor, Alfonso X, lo visité nuevamente con otro espíritu (…)

Los Templarios y la Mesa de Salomón. Capítulo 18.

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.
 

El castillo de Alcaudete tiene su origen en un pequeño enclave situado en la cumbre del cerro que hoy ocupa la fortificación, que contaría con construcciones sencillas, como empalizadas en tapial de tierra y mampuestos, con las que se reforzarían los puntos más accesibles. Estas estructuras han desaparecido, aunque pudieron ser reutilizadas para la construcción del conjunto defensivo erigido en época almohade.

En este período (s, XII-XIII) el núcleo de población se desplaza a media ladera, rodeándose con una cerca, mientras que en la cumbre se levanta un alcázar de planta poligonal con un cimiento escalonado. Los lienzos se reforzaron con torres macizas de planta cuadrada que se sitúan en los tramos rectos, a modo de contrafuertes de mampostería, y bestorres, torres abiertas por la parte posterior del baluarte, situadas en los ángulos de los muros, con cimiento de mampostería sobre el que se superponen paramentos de tapial de tierra. En el interior de este recinto se han localizado estructuras de muros de tapial, y un aljibe de planta rectangular.

A mediados del siglo XIII, la Orden Militar de Calatrava introdujo importantes modificaciones, revisten de mampostería las antiguas murallas que rodeaban la población, a la vez que amplían el número de torres que la defendían. Reutilizan el recinto del antiguo alcázar como antemuro, reduciendo significativamente su altura, y edifican una nueva fortaleza en su interior, dejando entre ambos un estrecho pasillo o liza.

La nueva fortaleza Calatrava desarrolla una planta poligonal, construida en mampostería irregular rejuntada con mortero de cal.  Estaba jalonado por seis torres, a las que se accedía desde los adarves que discurren sobre los lienzos de muralla y que permiten recorrer todo el recinto. Poseía dos puertas, la principal en el extremo norte, defendida por dos torres de planta cuadrada con esquinas redondeadas y una pequeña poterna en el extremo sureste, protegida por la conocida como Torre del Reloj.

La puerta principal conduce a un pasillo-foso, configurado por las murallas del propio castillo y los escarpes rocosos del interior, que definen una terraza o meseta central elevada, en la que se localizan los edificios más relevantes de la fortaleza, mientras que en un nivel inferior se localizan dos aljibes, uno de ellos bajo el cuerpo de guardia y otro adosado a la entrada de las caballerizas.

El patio o plaza de armas, situado en el extremo noroeste, es un espacio abierto en cuyas inmediaciones se edificó el cuerpo de guardia, un edificio de planta rectangular construido con mampostería irregular y conectado directamente con el adarve de la muralla noroeste. El claustro, emplazado en el sector sur, conformaba un pequeño patio situado en el entorno de la Torre del Homenaje y la Sala Capitular, del que solo se conserva algún elemento arquitectónico (columna y capitel). En las inmediaciones del claustro encontramos dos edificios, uno que albergó cocina, almacenes y alcobas, y otro con el nivel inferior dedicado a caballerizas y el superior ocupado por una gran Sala Capitular, a la que se accedía directamente desde el Claustro. En el sector oriental de la meseta superior, frente de la Torre del Homenaje, se localizaba el Oratorio y junto a él las cocinas y alcobas de la guarnición.

En el punto más elevado y central de esta meseta superior se ubica la Torre del Homenaje, de perfil troncocónico y planta rectangular, con muros de mampostería que llegan a alcanzar los tres metros de ancho. Se accedía a su interior por un patín adosado a la esquina Noreste. Al llegar a la altura de la primera planta, había que salvar un cadalso o balcón volado, mediante una plataforma retráctil de madera. La torre se estructura en tres plantas, la primera usada como almacén-aljibe, a la que se accede por una trampilla practicada en el pavimento de la estancia superior, la central como identificada como zona de tránsito y la superior que se relaciona como la residencia del comendador.

En época renacentista el castillo perdió su función militar, para convertirse en residencia palatina. Se construyen en su interior nuevas estructuras residenciales y palaciegas en el entorno de la torre del Homenaje, un complejo entramado selecto de estancias, patios porticados y corredores, al que se accedía tras vadear la denominada Puerta de la Reja y la entrada principal al área palatina. Colindando con las áreas nobles, se localizaban las dependencias de servicio, dotadas de almacenes, cocinas o cuadras, que ocupan el extremo noroeste y en las inmediaciones del cuerpo de guardia y la puerta del palacio. Estas reformas conllevaron la anulación de elementos precedentes, como el oratorio, el patín de la torre del homenaje o la poterna; la reducción de las dimensiones de otras, como ocurrió con el patio de armas o el pasillo-foso; o bien la compartimentación y cambio de funcionalidad de las caballerizas o la Sala Capitular.

Alcaudete se identifica con el municipio flavio de Sosontigi, nombre escrito en una inscripción honorífica, encontrada en la zona. Aunque no se han encontrado restos romanos en el núcleo urbano de Alcaudete, han sido numerosos los hallazgos en sus inmediaciones, principalmente en la zona del parque, instituto y polígono industrial.

Entre los siglos VIII y X, tras la conquista musulmana, fue conocido con el nombre de Hisn al–Qabdaq, un pequeño asentamiento emplazado en la cumbre del cerro que hoy ocupa el castillo, que aprovechaba las defensas naturales que le ofrecía su acusada orografía. Con la conquista almohade, el núcleo de población se desplazaría a media ladera, cercándose una muralla que lo protegía, mientras que en la cumbre se levantaría un alcázar sobre las estructuras defensivas preexistentes.

En la segunda mitad del siglo XIII Alcaudete se convierte en señorío de la Orden Militar de Calatrava, puesto que, a partir de su conquista, su gran importancia estratégica dentro de la frontera con el reino Nazarí de Granada, determinó que el monarca castellano Fernando III la entregara en 1246 a la Orden Militar de Calatrava, institución que promovería el amplio refuerzo de sus defensas.

A pesar de ello, en 1300 fue conquistada temporalmente por los ejércitos musulmanes, hasta que en 1312 fue recuperada por el Infante D. Pedro, siendo convertida por Alfonso XI en una villa de realengo. En 1385 el rey Juan I la donó en mayorazgo a D. Alfonso Fernández de Montemayor, Adelantado Mayor de la Frontera. La villa quedó adscrita al señorío de Montemayor hasta el siglo XVI, llegando a conseguir el título de condado en tiempos de Carlos I.

En el siglo XVII, bajo el dominio de los Fernández de Córdoba, la fortaleza-palacio fue languideciendo hasta su definitivo abandono. En el siglo XVIII el castillo se encontraba ya en estado de ruina. Desde finales del siglo XX ha sido objeto de un largo proceso de investigación arqueológica y restauración.