En el estratégico promontorio sobre el que se halla situada la villa-fortaleza de Castellar existió un asentamiento ibérico y, luego, una torre o puesto de vigilancia en época romana, como lo han demostrado los hallazgos realizados en el transcurso de varias intervenciones arqueológicas realizadas en el Castillo, consistentes en cerámica ibérica barnizada en rojo de los siglos IV y III antes de Cristo, varias tégulas romanas y una moneda del siglo I de la dinastía Flavia.

Las primeras referencias escritas del castillo de Castellar aparecen en las crónicas árabes de principios del siglo X. Refiere el historiador cordobés Ibn Hayyán que el 5 de mayo del año 914, Abderramán III, al frente de un poderoso ejército, después de haber atravesado las montañas de Málaga, "se aproximó al castillo de Lawra (hisn al-Larub) cerca del valle del río Guadiaro (Castellar), perteneciente a la cora de Algeciras. Como sus defensores habían huido, los hombres del sultán entraron en él y lo saquearon. Luego se dirigió a Algeciras, capital de la zona, entrando en la ciudad el jueves día 1 de junio del año 914, permaneciendo en ella unos días para atender a su gobierno y a su defensa costera… Umar ben Hafsún tenía en aquel puerto algunas naves que enviaba a la costa africana para aprovisionarse de cuanto necesitaban y que habían levado anclas para alejarse de las tropas omeyas… Pero fueron perseguidas y, una vez amarradas a la orilla, el emir las hizo quemar en su presencia. Esto fue visto desde las comarcas vecinas por la gente de Castellar, Casares y Gaucín provocando que se inclinaran a la obediencia". Unos años antes, el 8 de mayo del año 907, las tropas omeyas que se dirigían a la conquista de la capital marítima de los rebeldes (Algeciras) se acercaron, hostilizadas por los sublevados, a un castillo que estaba a una jornada de marcha de dicho puerto, que se conocía con el nombre de Hisn al-Larub (Castillo del Guadiaro) o al-Qasr.

El castillo o hisn que menciona Ibn Hayyán debía de tratarse de una fortificación de altura, situada en la cumbre del cerro donde hoy de halla la villa-fortaleza, aún sin las complejas y poderosas defensas que han pervivido hasta la actualidad. Entonces no sería más que un endeble reducto constituido por muros construidos, probablemente, a la piedra seca -lo que explica la facilidad con que lo tomaron las tropas del emir omeya-, erigido sobre las ruinas del asentamiento de época ibero-romana.

La mención, por Ibn Hayyán, de Castellar, Gaucín y Casares indica que, a principios del siglo X, eran muy numerosos estos hisn, la mayor parte de ellos habitados por bereberes desde los tiempos de la conquista de Hispania y por muladíes (cristianos convertidos al islam), edificados en las cimas de las sierras que discurrían entre Algeciras y Ronda. El geógrafo al-Udri, en el siglo XI, menciona en su obra varios distritos y castillos que pertenecían a la cora o provincia de Algeciras, entre ellos el hisn de Aruh, identificado como el castillo de Castellar, y el de Jushayn (Ojén).

Panorámica de la villa-fortaleza de Castellar tomada desde el Suroeste.

En cuanto a los diferentes topónimos empleados en la Edad Media para identificar a la villa-fortaleza de Castellar, además de los citados en la crónica de Ibn Hayyán, hay que mencionar a Ibn Said al-Magribí que, en su obra, escrita en el siglo XIII, hace referencia al castillo de Qastallub, situado en el distrito de Algeciras. Castillo de Qardala es un topónimo que encontramos en el Rawd al-Qirtas, crónica escrita por el historiador Ibn Abi Zar, refiriéndose a Castellar en el año 1293. Refiere este cronista que era uno de los reductos fortificados que el sultán de los meriníes, Abu Yaqub, entregó al rey de Granada, juntamente con el castillo de Jimena. Un año antes, el rey Sancho IV había exigido al de Granada la entrega de una serie de castillos enclavados en las proximidades del Estrecho, entre los que se encontraba uno denominado Qastala. El castellum romano pudo derivar en qasr al pasar a la lengua árabe (topónimo con que algunas fuentes musulmanas nombran, también, a Castellar), como turris pasó a ser turrus (topónimo muy abundante en época andalusí en la zona), girando con el transcurso de los siglos de la siguiente manera hasta llegar al actual Castellar: Qasr – Qasr Arub – Qastallub – Qardala o Qastala – Castellar. Lo cierto es que el nombre árabe de la fortaleza –Qastala o Qastallub– degeneró al pasar a la lengua de Castilla en el apelativo genérico de "Castellar" (lugar del Castillo), que encontramos escrito con frecuencia en las crónicas cristianas, entre ellas en la de Alfonso XI, cuando dice que "el Rey Ismael, por haber en su ayuda al Rey de allen mar, diole a Algeciras, et a Ronda, et a Castellar, et a Ximena, et a Estepona".

Torre del Homenaje con el mirador construido en el siglo XIX.

En las cartas que el rey Juan II envía, entre 1434 y 1456, al concejo de Jerez de la Frontera para que se haga cargo de la defensa de la fortaleza y en varios acuerdos del Ayuntamiento de esa ciudad aparece nombrada la villa como "Castellar" o "el Castellar". En cuanto al genitivo aclarativo "... de la Frontera", desconocemos cuando comenzó a utilizarse, aunque el término "Frontera" aparece ya mencionado en el siglo XIII para referirse a la zona de separación entre las tierras dominadas por el Islam y las posesiones castellanas en el sur de Andalucía. Sin embargo, la utilización, en el caso de Castellar, de este término es muy tardía. Probablemente no se empleó hasta finales del siglo XIX, pues en la documentación del siglo XV conservada en el Archivo Municipal de Jerez de la Frontera y de los siglos XVI, XVII y XVIII en el Archivo Municipal de Castellar y en el Archivo Ducal de Medinaceli, siempre aparece como "mi villa de Castellar" o la "villa del Castellar" sin el apelativo "de la Frontera" que, en cambio, sí acompañaba a Jerez en la documentación del siglo XV. Tampoco aparece en el privilegio de concesión del señorío a don Juan de Saavedra en 1445, ni en el diploma de otorgamiento del condado de 1539, ni en la "Escritura de Concordia" de 1549. En el libro 561 de las Respuestas Generales del Catastro de Ensenada, realizado en 1752, se menciona sólo a la "villa de el Castellar".

En cuanto al recinto defensivo conservado, se puede decir que se adapta a las irregularidades del terreno, tendiendo su planta a la forma de un pentágono de lados desiguales, más largos los que miran al Este y al Oeste. El alcázar se halla situado al Nordeste de la fortificación, a caballo de la puerta de entrada a la villa, cerrando con su poderosa estructura la fachada septentrional del enclave fortificado. Los lienzos que miran al oriente y al occidente son continuación del barranco o escarpadura que rodea por esas zonas el promontorio sobre el que se haya enclavada la villa–fortaleza. Las fachadas norte y sur, por encontrarse en terrenos más llanos y accesibles, se han reforzado con barreras o antemuros, corachas, torres exentas y muros con saeteras. La puerta de la villa, que se abre debajo del alcázar, se ha fortificado, además, con un sistema defensivo constituido por dos torres, una de ellas de ingreso recto y otra con pasadizo en recodo, más los respectivos muros que las conectan.

La muralla, las torres de flanqueo, los antemuros o barbacanas, el alcázar y el sistema de puertas de aparato con pasadizo en zig-zag que defendía el acceso hasta la puerta de la villa, fueron edificados a lo largo del siglo XIII o principios del XIV, bien por los meriníes, que fueron dueños de toda la comarca entre los años 1275 y 1306, o los nazaríes que les precedieron en el poder y, luego, los sustituyeron.

- Torre con puerta de ingreso recto.

El recinto exterior está reforzado, cada veinte metros aproximadamente, por nueve torres de flanqueo que presentan tipologías y tamaños muy variados, de las cuales, siete tienen planta cuadrada o rectangular con una anchura de entre 3,5 y 4,5 metros. Algunas de ellas muestran partes reconstruidas en época tardía, posiblemente por haber sufrido daños causados por algún asedio; otra, es una torre atípica de planta semicircular, que debió ser erigida en época cristiana, y la última, que fue utilizada como torre-fuerte habitable, es la llamada torre de Medina, un torreón que domina la esquina suroeste del recinto con una base cuadrada de seis metros de lado, defendida por un potente antemuro.

El alcázar es un edificio de planta tendente a naviforme. Fue, durante siglos, la residencia del alcaide musulmán y, luego, de los condes de Castellar. Del inmueble destacan la mansión nobiliar, recrecida después de la conquista en 1434, la torre del Homenaje (reformada en el siglo XIX) y el llamado en la "Relación de Fortalezas de 1504" Edificio Nuevo, una ampliación del alcázar, de planta casi cuadrada y notable altura, erigido al noroeste del mismo a finales del siglo XV o principios del XVI. El cuerpo superior del alcázar -en la parte situada sobre la puerta de la villa y en la que mira a la plaza de Armas-, se abre al exterior por medio de ventanas con arcos de medio punto de ladrillos de clara factura cristiana. Esta segunda planta del edificio nobiliar debió construirse entre los siglos XV y XVI.