El castillo de las Navas de Tolosa está conformado por un recinto amurallado con forma de trapecio y una torre de planta hexagonal situada en su ángulo noreste. Posiblemente existía un segundo recinto externo al que pertenecerían algunos lienzos visibles en el entorno del castillo.

El recinto de la fortificación, muy destruido, posiblemente fue construido en  tapial de argamasa sobre un basamento de mampostería, se adapta a la meseta rocosa sobre la que se asienta, utilizándola como cimentación y como parte de su defensa. En su interior se distinguen algunos tramos de muros que pertenecerían a dependencias internas y un posible aljibe. 

Se conservan dos accesos al interior de la fortaleza, la puerta principal estaba situada en su lado oeste, protegida por un muro acodado que apoya en un escarpe de roca natural. En el flanco oriental, junto a la torre, se abre una estrecha poterna parcialmente oculta por una roca que le da protección visual y crea un pasillo acodado para llegar hasta ella.

La torre, construida en un tapial muy compacto por su alto contenido de cal, conserva unos 14 m de alzado desde el exterior y tan solo dos desde el interior. En el enlucido exterior de la torre se aprecian aún unas líneas que formarían parte de algún tipo de decoración o simulación de grandes sillares, técnica conocida como falso despiece, sobre todo en la zona de la poterna. 

En su interior existe un espacio rectangular que ocupa gran parte de la estancia, dejando un pasillo estrecho que lo rodea. Posiblemente se trate de un aljibe para recoger y almacenar el agua de la lluvia, cuya cubierta sostendría el suelo del primer piso de la torre. 

Al noreste de la fortaleza se observan vestigios de un edificio rectangular con divisiones internas, quizá la ermita que se erigió poco después de la conquista cristiana. Otros muros que se distinguen en su entorno podrían evidenciar la existencia de una pequeña alquería. 

La zona de Despeñaperros ha atraído pobladores desde la Prehistoria por su escarpada orografía, en la que proliferan cuevas y abrigos, como por sus parajes naturales propicios para la sacralización. 

Pero fue su valor estratégico respecto a los pasos naturales que atraviesan Sierra Morena, por lo que se erigieron fortificaciones durante la Edad Media, e incluso en períodos anteriores, con el objetivo de controlar las vías de comunicación entre la Meseta y al-Ándalus. 

Aunque la pequeña meseta pudo estar habitada ya en la Edad del Bronce y en época romana, el Castillo de Navas de Tolosa, sería construido entre los siglos XI-XII por los musulmanes para el control de los pasos naturales de Despeñaperros. Años después, estos reforzarían su papel defensivo en un intento de frenar el avance de las tropas cristianas. Esta fortaleza se convirtió en una de las que “puertas” del paso del Muradal, junto con Castro Ferral, lo que le convertía en un objetivo a batir. Tras la batalla de las Navas de Tolosa quedará definitivamente en poder de Castilla. 

La fortaleza formó parte del escenario de uno de los hitos más destacados de la historia medieval peninsular, por su trascendencia en el avance de los reinos cristianos sobre al-Ándalus, la batalla de las Navas de Tolosa, librada el 16 de julio de 1212. Concebida como cruzada, fue una contienda en la que las rutas y pasos hacia la Meseta jugaron un papel fundamental. En ella se enfrentaron una coalición de reyes cristianos, Alfonso VIII de Castilla, Pedro II de Aragón y Sancho VII de Navarra, apoyados por el papa Inocencio III, contra el califa almohade Muhammad al-Nasir, en cuyo ejército se integraron combatientes procedentes del Magreb, de territorios subsaharianos y de contingentes turcos.

El 12 de julio de 1212, tropas al mando de Don Diego López de Haro tomaron el Puerto del Muradal. Dos días más tarde, tras ser bloqueados en el paso de la Losa, los cristianos acampan en el paraje conocido como Mesa del Rey, desde donde acudieron a la batalla, derrotando al ejército almohade.

Tras la victoria de los ejércitos cristianos, la fortificación de las Navas mantendría su importancia en la ruta del Muradal a lo largo del siglo XIII, convertida en uno de los puntos estratégicos para el control del paso de tropas durante la conquista del Alto Guadalquivir. En 1217 el arzobispo de Toledo se adjudicó los castillos de la región, con el consentimiento del papa Honorio III, quien los confirmó como límites de la archidiócesis toledana. 

Según las fuentes escritas este espacio fue repoblado por contingentes castellanos a lo largo del siglo XIII, derribándose su castillo en 1473 por mandato de la Ciudad de Baeza.