Esta imponente fortaleza se levanta en el extremo meridional de un cerro que sirve de asiento también a la población actual. Esta posición que forma parte de las primeras estribaciones de Sierra Morena, controla el valle del rio Rumblar, pero sobre todo, la planicie que se extiende hasta Bailén y Linares y el Guadalquivir y que es la vía de comunicación desde el valle de este río hacia los puertos que atraviesan la sierra en dirección al Campo de Calatrava.
Antes de pasar este lugar a poder de los almohades en 1157, una posible fortaleza anterior fue conquistada por Alfonso VII en 1147. El actual castillo fue tomado de nuevo por Alfonso VIII en 1189 y recuperado por los almohades en 1212 justo antes de la batalla de Las Navas de Tolosa, permaneciendo a pesar de ello en su poder hasta su conquista definitiva por Fernando III en 1225.
El castillo tiene una planta con forma de almendra, con una dimensión máxima en la dirección norte-sur de 103,80 m y una anchura máxima de 43,30 m. Su perímetro, más rectilíneo en el lado oriental y más abombado en el occidental, está defendido por 15 torres, de las que dos ocupan los picos de la almendra, siete flanquean el lado occidental y seis el oriental. En medio de este se abre la puerta entre dos torres que se aproximan entre sí más que las demás. La torre más septentrional del recinto quedó sustituida por otra torre de mayor tamaño y altura, ya en época cristiana, a modo de torre del homenaje. Es muy probable que la torre musulmana quedara embebida dentro de la construcción posterior. Un dibujo del siglo XVII realizado por Martín Ximena Jurado representa un antemuro, al menos en el frente meridional de la fortaleza, hoy prácticamente desaparecido.
Las torres son sensiblemente cuadradas, resultando bastante prominentes hacia el exterior del recinto y están huecas en toda su altura, aunque el espesor de sus muros se va reduciendo a medida que se asciende. Albergaban tres habitaciones superpuestas, que estaban separadas entre sí por forjados de madera, hoy desaparecidos, salvo alguno reconstruido modernamente. Para cerrar superiormente las torres y sostener las terrazas hay bóvedas de cañón hechas de ladrillo, siendo prácticamente el único lugar en que se recurre a este material. Cada habitación posee una puerta independiente abierta hacia el interior del castillo que carecen de dinteles siendo el propio hormigón el que conforma los huecos. A las salas bajas se entra directamente desde el suelo del espacio interior. Al piso intermedio se debía subir mediante escalas de madera móviles. Las salas superiores tienen acceso desde el adarve general de la muralla que recorre todo el perímetro a la misma altura. Desde las habitaciones superiores y a través de pequeños huecos abiertos en la bóveda se accedía a las terrazas de las torres también mediante escalas. Las habitaciones intermedias y altas disponen de saeteras, generalmente una en cada frente, aunque sin seguir una pauta regular.
El espesor de los muros de las torres varía entre 1,10 m en la zona baja y 0,85 en la alta y se reduce a 0,45 m en el peto de las terrazas y a 0,35 m en las almenas. El grueso de la muralla que discurre entre las torres y por detrás de estas es de 1, 40 m aproximadamente. Su altura varía según los tramos y la topografía del terreno, pero llega en alguna zona a superar los 10 m, mientras las torres se elevan 2,40 m sobre el nivel de los adarves de la muralla. Estos tienen un recorrido prácticamente horizontal, con un ligero descenso desde el sur hacia el norte siguiendo el desnivel que presenta el terreno.
Toda la construcción islámica está realizada con obra de tapia de hormigón de cal de muy buena calidad y gran resistencia como lo prueba el buen estado general de conservación con que ha llegado hasta nuestros días. Los cajones de la tapia tienen una altura de entre 0,80 y 0,84 m y estaban recubiertos con un fino enlucido de cal sobre el que se marcaban falsas juntas que definían grandes sillares con la misma altura que la de los cajones. De ellas solo quedan algunas líneas de replanteo y en ciertos sitios los golpes de paleta en espiga que facilitaban la adherencia del mortero en relieve con el que se hacían las falsas juntas.
Como ya se ha indicado, la puerta principal del castillo se sitúa en el centro del lado oriental. Se encuentra flanqueada por dos torres, de factura similar al resto, pero dispuestas a menor distancia, dejando un espacio de sólo 4,50 m. En ese espacio se dispuso una bóveda de 3,10 m de luz y 1,30 de fondo cuyo frente presenta forma de herradura, aunque después es de medio punto. En el testero de fondo de esta bóveda se encuentra el arco de la puerta propiamente dicha que tiene una anchura de 1,90 m. y adopta la forma de arco de herradura con impostas en forma de nacela sencilla. Después de traspasar este arco hay una bóveda de mayor altura, de perfil apuntado sin impostas marcadas.
Todo el conjunto de la puerta aparece hoy realizado en mampostería de piedra, que en muchas zonas se puede incluso considerar de sillería de labra no demasiado esmerada. Sin embargo, todo ello parece haber sufrido importantes labores de restauración cuyo alcance resulta difícil de precisar y que hace casi imposible una adecuada “lectura de paramentos”. Alguna fotografía antigua muestra, en la cara interior de la puerta, que la mampostería recubre aparentemente obra de tapia, pero es casi imposible deducir de ello una adecuada lectura estratigráfica. Este paramento interior de mampostería se encuentra ligeramente retranqueado respecto al paramento interno de la muralla. Sobre la puerta existe un ámbito o habitación, hoy sin cubrición, al que parece se accedía desde las habitaciones intermedias de las torres de flanqueo. Estas presentan en su frente ventanas en vez de aspilleras. Esto permitiría suponer que tales espacios pudieron usarse como habitaciones de vivienda, quizás destinadas al alcaide de la fortaleza.
En el lado opuesto del castillo, casi enfrente de la puerta principal, existe un hueco de 1,20 m de ancho por 1,60 de alto, que parece funcionó como poterna. Por el exterior su umbral se encuentra a más de 1,30 m del suelo por lo que solo podía ser usado por personas y no por caballerías.
En el interior de la fortaleza hay un aljibe subterráneo situado en una posición central, algo desplazada hacia el suroeste. Es de dos naves comunicadas por un arco. Las excavaciones realizadas en el interior han puesto de manifiesto, aparte de estructuras de épocas anteriores, la existencia de un conjunto de edificaciones que ocupaban casi todo el espacio disponible dejando algunas calles de circulación y un espacio libre a modo de plaza en donde se encuentra el aljibe.
Tras la conquista definitiva del castillo por parte de Fernando III en 1225, y en una fecha desconocida, se construyó una torre del homenaje en el extremo septentrional, suplantando y seguramente embebiendo dentro de su fábrica la primitiva torre islámica. Esta torre, construida con mampostería de piedra, es maciza hasta el nivel de los adarves de las cortinas contiguas y cuenta con dos pisos con salas interiores abovedadas. En el piso superior existieron ladroneras a las que se accedía desde la sala interna. Con las edificaciones del interior ya destruidas, se construyó en la parte norte una nueva muralla interna con un gran cubo circular que encerraba un reducido alcázar que aparentemente no se llegó a concluir.
Existe cierta controversia respecto a la adscripción cronológica de este castillo. La historiografía tradicional lo atribuye a época califal omeya en base a una inscripción que recogió la Real Academia de la Historia en el siglo XIX, hoy en el Museo Arqueológico Nacional, que se suponía procedente de esta localidad. En todo caso, esta datación ha servido de base para considerar también califales otros castillos como el de El Vacar. Un artículo de A. Canto e I. Rodríguez Casanova puso en duda tal procedencia afirmando que existe una confusión con otras inscripciones. Esta suposición ha llevado a replantear la cronología del castillo a este y otros autores, avanzándola a época almohade. Aunque esa hipótesis ha sido rebatida a su vez por J. F. Muñoz-Cobo, persiste la duda de que en todo caso la inscripción se refiera realmente al castillo que hoy vemos, ya que se recogió de otro lugar de la población y no hay ninguna huella o indicio de que pudo estar fijada en algún lugar del mismo. Con independencia de que la mencionada inscripción provenga realmente de Baños de la Encina y considerando que pudiera estar relacionada con otra fortificación anterior, de este u otro lugar, conviene analizar los datos arqueológicos que ofrece el castillo para tratar de datarlo.
Ni la tipología de las torres ni el material utilizado en la construcción avalan la datación omeya. En los castillos y fortificaciones conocidos y bien datados de esa época, como la alcazaba de Mérida, el castillo de Tarifa, las murallas de Madīnat al-Zahrā’ o el castillo de Gormaz, las torres son macizas, resultan poco prominentes respecto a las cortinas y sus adarves tampoco sobresalen en altura respecto a los de los lienzos de muralla contiguos. Tampoco contamos en época emiral o califal con fábricas de tapia de hormigón de cal de la calidad y consistencia que muestran las de este castillo. Existe constancia de fábricas de tapia en el castillo de Gormaz, de un momento anterior a la reforma califal que las forró con buena sillería. Pero era tapia de tierra que ha desaparecido por su poca consistencia. Las fortificaciones levantadas por el estado cordobés tanto en la capital como en las marcas o en el Estrecho son de características constructivas totalmente distintas, predominando la buena sillería dispuesta al modo cordobés o en formas que se le asemejan.
Frente a ello, existen numerosos y variados ejemplos de fortificaciones almohades hechas con tapia, de mejor o peor calidad, pero muy semejantes a las de este castillo. Las falsas juntas aparecen con asiduidad en muchos de ellos, así como las torres sobreelevadas respecto a los adarves de las cortinas y con cámaras interiores. Son innumerables las torres defensivas construidas por todo el Levante peninsular, con buenos hormigones de cal y fechables en los siglos XII y XIII. Sirvan como ejemplo las de Villena o Biar. De perfil muy parecido a las torres del castillo son las levantadas en las inmediaciones de Segura de la Sierra. Las fortificaciones de Sevilla o Córdoba son también buenos paralelos. Finalmente, la visión en alzado del castillo con los perfiles inclinados de las torres en retranqueo, típico de muchas construcciones en tapia, no deja de recordar las imágenes de los qusur marroquíes de la zona del Atlas.
Podría caber la duda de si la puerta, de aspecto muy arcaizante, pudo pertenecer a una fortificación anterior, pero tampoco puede descartarse que esas mismas formas simples se hayan seguido usando en época almohade. Como ya se ha indicado, la restauración realizada hace difícil distinguir esa posible diacronía.