Desde la antigüedad, Castellar era un enclave estratégico utilizado por los romanos para controlar el valle del río Guadarranque y la calzada que unía Carteia con Oba (Jimena) y Arunda (Ronda). Pero la arqueología y la existencia de numerosos abrigos con pinturas rupestres esquemáticas halladas en los entornos del castillo han evidenciado la ocupación del inexpugnable promontorio en el que se halla en la actualidad la villa fortificada de Castellar de la Frontera, de poblaciones anteriores a la presencia romana: Paleolítico en las dehesas de la Almoraima y el Olivar y cerámica de la Edad del Bronce e ibérica en los hallazgos realizados por el padre Sotomayor en el subsuelo del castillo en 1977 y en otras recientes excavaciones. Es muy probable que en la cima del cerro hubiera existido una torre edificada por los romanos para la vigilancia de la vía de comunicación antes citada, pero eso es algo que hasta ahora la arqueología no ha podido demostrar.

No cabe duda de que los invasores árabe-bereberes, en su avance hacia el norte, debieron ocupar tan estratégico enclave, bien documentado (aunque con diferente denominación) desde, al menos, mediado el siglo IX. De la importancia que, desde el punto de vista militar, tenía la fortaleza, lo evidencian las palabras del padre mercedario fray Pedro de San Cecilio, que en el año 1669, escribió lo que sigue: "En la cumbre de uno de estos montes, en el más eminente, está la villa de Castellar, de pequeña vecindad, y de ella corre la vista tan licenciosa, que de esta parte, y la otra del mar de Levante, alcanza los reinos de Sevilla, Granada, Gibraltar, Algeciras y Fez e Imperio de Marruecos".

Las élites árabes y sirias que encabezaban el ejército invasor, entre los años 711 y 712, se asentaron -frecuentemente mediante pactos y capitulaciones firmadas con los hispano-visigodos- en las zona urbanas y más ricas, mientras que los numerosos inmigrantes bereberes, escasamente islamizados, se establecieron en las regiones montuosas, más pobres, Las sierras situadas al norte de al-Yazira al-Jadrá y toda la serranía de Ronda fueron ocupadas por grupos tribales pertenecientes a las hawwara, masmuda, hinana o sinhaya. Según el geógrafo al–Yaqubi, que escribió su obra a mediados del siglo IX, "la región montañosa de Algeciras estaba poblada, en parte, por tribus bereberes". Otra fuente de la época incide en que estos bereberes pertenecían al grupo tribal de los Baranis. El amplio linaje de los bereberes kinanas se hallaba repartido por varias regiones de Andalucía, siendo los montes de Algeciras unos de los territorios donde más preponderancia adquirió. Estas noticias vienen a confirmar que la población de Castellar, Jimena y Gaucín, entre otros enclaves de la serranía situada entre Algeciras y Ronda, en los primeros siglos de la historia de al-Andalus estaba constituida por inmigrantes bereberes llegados con el ejército expedicionario de los generales Tariq ben Ziyad y Musa ben Nuzayr, lo que explicaría su proclividad a la disidencia y la rebelión y su oposición a someterse a los emires omeyas establecidos en Córdoba, al menos, desde mediados del siglo IX.

Pinturas esquemáticas antropomorfas y zoomorfa de la Cueva del Arquillo (Castellar de la Frontera).

Los bereberes que se asentaron en la cima del monte donde luego se erigió la fortaleza de Castellar, probablemente sobre las ruinas de una torre o edificación ibero-romana anterior, pronto construirían, para su defensa, un recinto amurallado a la piedra seca, cuyo nombre desconocemos, pero que aparece en las fuentes árabes como un hisn (castillo). Este primitivo castillo formó parte, entre los siglos VIII y X, de la cora o provincia de Algeciras, que abarcaba el actual Campo de Gibraltar más los municipios de Gaucín, Estepona, Marbella y parte de Alcalá de los Gazules. El geógrafo al-Udri, en el siglo XI, menciona en su obra varios distritos y alquerías que pertenecieron a la cora de Algeciras, entre ellos el de Aruh o del Guadiaro (que él identifica como el castillo de Castellar) y el de Jushayn, que se relaciona con Ojén (en Los Barrios).

Pero en el año 880 un caudillo de origen hispano, Umar ben Hafsún, se alzó contra el poder y la autoridad del emir de Córdoba, estableciendo su capital rebelde en la sierra malagueña, en la fortaleza de Bobastro. En poco tiempo logró atraer a su obediencia a numerosos castillos, aldeas y ciudades, desde Almería a Algeciras. Estas fortalezas rebeldes estaban habitadas por bereberes, muladíes o mozárabes cristianos descontentos con el trato que recibían de los emires omeyas, pues tenían que soportar impuestos abusivos, al margen de no sentirse parte del nuevo estado musulmán. En la cora de Algeciras sabemos que se unieron a Umar ben Hafsún la capital, Algeciras, y los castillos de Casares, Castellar, Jimena y Gaucín. Para algunos historiadores y arabistas, este levantamiento fue, sobre todo, una rebelión social del campesinado de Andalucía Oriental, agobiado por el duro censo fiscal sobre la tierra impuesto por el emir de Córdoba, a la que luego se añadieron factores de índole religiosa, política y étnica y que, al cabo, convirtieron la sedición en un movimiento de carácter nacionalista que fracasó cuando tomó el poder el emir Abderramán III.

Dos monedas bajoimperiales halladas en la villa de Cotilla (Castellar de la Frontera) en 1979 acuñadas durante los reinados de los emperadores Valente (328–378 d. de C.) y Honorio (393–423 d. de C.).

El gran historiador cordobés, Ben Hayyán, escribió en su extensa obra, en diez volúmenes, Al-Muqtabis fi tarij al-Andalus, que 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 situado en el valle del Guadiaro y que se conocía con el nombre de Hisn Lawra o Hisn al-Larub (castillo del Guadiaro, identificado como Castellar). Al día siguiente fueron ejecutados unos bereberes que llevaban abastecimientos a los defensores de la fortaleza. También dice que los rebeldes que guardaban el castillo resistieron valientemente los ataques omeyas durante seis días. En otro pasaje de la crónica se cuenta que la resistencia del castillo y el mal tiempo obligaron al ejército cordobés a retirarse desde al–Qasr (El Alcázar) hacia la costa en junio del mismo año. Ambos topónimos (Hisn al–Larub y al–Qasr) se refieren a una misma fortaleza. Esta hipótesis viene a confirmarse si observamos que el único emplazamiento posible, tierra adentro y a una jornada de marcha de Algeciras (para un ejército de la época: entre 20 y 25 kilómetros), era el de Castellar.

En otro capítulo de su crónica, Ben Hayyán dice que "en el año 907 Abán, hijo del emir Abd Alláh, dirigió una aceifa o expedición punitiva contra los distritos de Algeciras. Al frente de la caballería iba un tal Ahmad ibn Muhammad. Hizo alto en Algeciras el viernes 7 de mayo y el 16 de ese mismo mes se dirigió a la fortaleza de (Hisn al-Lawra) a la que sometió a combate y asedió y en la que dio muerte a un grupo de personas de las que la habitaban".

Una vista de Castellar con Gibraltar al fondo (Litografía de E. E. Napier sacada de un dibujo de W. Watson. Londres, 1839).

Habría que esperar hasta el año 914 para que Castellar (Hisn al–Lawra o al–Qasr), al mismo tiempo que Algeciras –puerto de conexión de los rebeldes hafsuníes con la otra orilla, de donde les llegaba ayuda en armas y alimentos de los enemigos fatimíes– y los demás castillos de su distrito pasaran definitivamente a estar bajo el control del emir de Córdoba. Refiere el citado historiador, que, "después de someter Abderramán III a los defensores de varios castillos en la sierra de Málaga, se desplazó hasta el castillo de Hisn al-Lawra (al-Qasr o Castellar), cuyos defensores habían sido avisados de la próxima llegada de las tropas emirales. Aunque la caballería de Abderramán se acercó a la fortaleza durante la noche, al llegar al pie de las murallas se percataron de que los rebeldes habían huido y buscado refugio en las alturas de la sierra vecina. Después de entrar en el castillo y saquearlo, marchó el ejército con dirección a Algeciras, capital de la provincia que aún se hallaba en la obediencia del rebelde de Bobastro, entrando en ella sin que sus habitantes opusieran resistencia el día 1 de junio del año 914. El emir permaneció en Algeciras varios días para reorganizar el gobierno y administración de la ciudad y su defensa costera".

Refiere Ben Hayyán que Ben Hafsún y los suyos tenían en aquellas costas algunas naves que enviaban a la orilla africana a comerciar y aprovisionarse, surtiéndose de lo necesario, por lo que el emir mandó soldados a buscarlas y tomarlas, pues los canallas habían huido con ellas al mar. Una vez amarradas a la orilla, las hizo quemar todas en su presencia con gran quebranto de los malvados que perdieron tal provecho. Esto fue visto desde las comarcas vecinas por la gente de Casares, Castellar y Gaucín y otros rebeldes de los entornos de Algeciras, provocando su desilusión y el que se inclinasen a la sumisión, a la que se acogieron enviando sus delegaciones a Abderramán III, que aceptó su arrepentimiento y les concedió su perdón. De este relato se desprende que las fortalezas de las sierras cercanas a Algeciras –entre ellas la de Castellar– se encontraban en la primavera del año 914 en la obediencia de Umar brn Hafsún, siendo sometidas por el emir de Córdoba en aquel verano para no volver nunca más a las filas del rebelde de Bobastro que falleció en el año 918.

En cuanto a los diferentes topónimos empleados en la Edad Media para identificar a la villa-fortificada de Castellar, además de los citados en este artículo, en el siglo XIII Ibn Said al-Magribí lo menciona con el topónimo QASTALLUB; el historiador Ibn Abi Zar, en el año 1293, lo cita como QARDALA; en la Crónica del rey Sancho IV aparece mencionado como QASTALA y en la Crónica del rey Alfonso XI, en 1343, ya aparece como CASTELLAR. El genitivo aclarativo "…de la Frontera" es muy tardío. No aparece en la documentación hasta el siglo XIX.

Sepulturas talladas en la roca, probablemente tardoantiguas o medievales halladas en la sierra de Montecoche.