Desde que, a mediados del siglo VIII, el primer emir de al-Andalus, Abderramán I, dividió en "coras" o provincias las tierras conquistadas a este lado del Estrecho cuarenta y cinco años antes, la región que hoy conforma el Campo de Gibraltar más los términos actuales de Gaucín, Estepona, Casares y parte de Alcalá de los Gazules, se constituyeron en una estratégica provincia con capital en la ciudad portuaria de al-Yazira al-Jadrá. A esta provincia pertenecían numerosos distritos, entre ellos los de Aruh, de los Banu Hirmaz, de Labtit, de Maqrun y de al–Barbar (o de los bereberes). El geógrafo al-Udri también menciona las alquerías de Mayshar (Almarchal, cerca de Tahivilla), Mashalis, Jushayn (Ojén) y los castillos de Castellar, Utaba (Oba-Jimena), Gaucín y Casares. En la capital de la "cora" residían el gobernador y el cadí o juez provincial, el centro del poder religioso y jurídico (la mezquita aljama) y el alcázar, residencia del poder político y militar.

A una jornada de marcha, al norte de la capital, cerca de la antigua calzada que unía Carteia e Iulia Traducta con Arunda y Córdoba, se encontraba el hisn (castillo) de Castellar encaramado, como lo estaban Jimena y Casares, en la cumbre de una enriscada sierra. Desde sus murallas se divisaba tan dilatada extensión de territorio que los gobernadores de la "cora" no dudarían en establecer en aquel lugar un puesto de observación que, por medio de ahumadas, se pudiera comunicar con los otros castillos y torres cercanas y con la propia capital.

Los territorios de Castellar, Jimena y Gaucín estaban poblados, durante el Emirato, por una población heterogénea, formada por bereberes -siempre proclives a la insurrección-, e insatisfechos indígenas hispanos (los pocos árabes llegados de Oriente se habían establecido en las ciudades), lo que explicaría la tendencia de los habitantes de las zonas montuosas y aisladas a las rebeliones y a las continuas revueltas documentadas en la provincia algecireña entre mediados del siglo IX y principios del siglo X.

En la región norte del Estrecho, además de los numerosos inmigrantes bereberes llegados desde la otra orilla (algunos, como Yahya ben Katir, de la tribu masmuda, llegaron a ostentar los cargos de gobernadores de la ciudad o jueces), continuaron asentados pobladores hispanos que pudieron conservar su propia religión (la cristiana), su lengua (que era el romance), sus costumbres y sus propiedades a cambio de rendir pleitesía al Califa de Damasco y pagar un impuesto especial -la yizya- que obligaba solo a los cristianos y a los judíos. Los cristianos que continuaron gozando de libertad de culto y conservaron sus propiedades fueron llamados mozárabes. Sin embargo, un sector de la población cristiana se convirtió al islam, siendo conocidos como muladíes.

Los emires de Córdobas exigían el pago del impuesto de la yizya solo a los cristianos y judíos de al-Andalus.

Bereberes, mozárabes y muladíes -la mayoría de los habitantes de la "cora" yazirí- constituyeron, a lo largo de los siglos VIII y IX, comunidades descontentas que encabezaron frecuentes rebeliones contra el poder central de Córdoba, manteniendo las sierras del sur en continuo estado de guerra durante casi cincuenta años. En ese período de tiempo, el espacio geográfico que hoy conforma el Campo de Gibraltar fue testigo de una enconada lucha entre los rebeldes y los omeyas cordobeses, siendo Castellar, Jimena, Gaucín y Casares, algunos de los enclaves más contumaces del sur del emirato.

Estas rebeliones estaban fomentadas, principalmente, por el malestar existente entre los bereberes y los muladíes asentados en las zonas montañosas por cuestiones fiscales. Esto provocó que los distritos del sur del Emirato emprendieran una serie de levantamientos que, en algunos momentos, mantuvo toda la región meridional de al-Andalus fuera del control de las autoridades de Córdoba. La "cora" de Algeciras fue una de las zonas más proclives a las rebeliones, donde se sucedieron alzamientos, incluso en la misma capital.

Abderramán III según un grabado del siglo XIX.

Pero la insurrección que alcanzaría los dos tercios del territorio andalusí y que pondría en peligro el propio Estado Cordobés, iba a tener como principal escenario las serranías de Ronda, Málaga y Algeciras y, como núcleo central, la ciudadela de Bobastro. Se trata de la rebelión de un personaje de origen hispano y cristiano, Umar ben Hafsún, aunque de una familia conversa al islam, que se alzó contra el poder de los omeyas en el año 880 logrando atraer a su causa a numerosos descontentos muladíes, mozárabes y bereberes.

Muchos castillos de la serranía se unieron al caudillo andaluz en su lucha contra el gobierno cordobés. Desde Algeciras a las Alpujarras, a todo lo largo de la cordillera Penibética, los inexpugnables castillos roqueros y algunas ciudades se alzaron en rebelión, manteniendo en jaque, durante casi cincuenta años, a los emires omeyas Muhammad I, Almúndir, Abd Allah y Abderramán III.

En la primavera del año 888, el emir Almúndir abandonó Córdoba con su ejército y marchó en persona contra los insurrectos, aunque, después de algunas escaramuzas, firmó la paz con ellos. Pero, al poco tiempo, los rebeldes atacaron a Abu Harb, uno de los más leales servidores del emir, que era gobernador en una fortaleza de la "cora" de Algeciras, apoderándose de ella.

Se tiene constancia de que los habitantes de Castellar, como los de otras fortalezas de su entorno, como Gaucín y Casares, participaron en la rebelión del señor de Bobastro, sufriendo en varias ocasiones el asedio del ejército cordobés. El 8 de mayo del año 907, las tropas omeyas, que se dirigían a la conquista de Algeciras, que se había unido a la rebelión, se acercaron, hostilizadas por los sublevados, a un castillo que estaba a una jornada de marcha de esta capital, situado en el valle del Guadiaro, y que era conocido con el nombre de Hisn Lawra o Hisn al-Larub (castillo del Guadiaro–Castellar). También en ese año, Abán, hijo del emir 'Abd Allah, 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ó al castillo de Castellar, al que asedió y dio muerte a muchos de los que lo habitaban.

Habría que esperar hasta el año 914 para que Castellar, al mismo tiempo que Algeciras —puerto de conexión de los rebeldes con los fatimíes norteafricanos— y los demás castillos de sus distritos pasara definitivamente a estar bajo el control del emir de Córdoba. Algeciras y los castillos de su “cora” eran, en los años finales del siglo IX, un territorio de enorme importancia estratégica para los Omeyas, donde se localizaba el principal puerto de conexión de los sublevados con sus aliados de la otra orilla por donde les llegaba el apoyo ideológico y la ayuda en armas y vituallas.

Castillo de Gaucín, uno de los sublevados contra el emir de Córdoba a principios del siglo X.

Ocupar la ciudad y su puerto y dominar las fortalezas erigidas en las sierras cercanas, debía de ser uno de los objetivos prioritarios del proyecto político de Abderramán III, consistente en lograr el final de aquella guerra civil y la definitiva pacificación de al-Andalus. En el año 914, después de haber nombrado como jefe de la expedición a general Badr ben Ahmad, el emir omeya se dirigió a las tierras controladas por Umar ben Hafsún y atacó varias fortificaciones aliadas del rebelde; unas se entregaron sin oponer resistencia y otras tuvieron que ser expugnadas por la fuerza de las armas. Refiere el gran historiador cordobés Ben Hayyán, que, a continuación se desplazó hasta el castillo de Castellar, cuyos defensores habían sido avisados de la proximidad de las tropas emirales. Aunque la caballería de Abderramán se acercó a la fortaleza durante la noche, al llegar al pie de sus murallas se percataron de que los rebeldes habían huido y buscado refugio en las alturas de la sierra. Después de entrar en el castillo y saquearlo, marchó el ejército en dirección a Algeciras, capital de la provincia, que 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 capital y su defensa costera. Ben Hayyán relata con las siguientes palabras las acciones llevadas a cabo por el emir en la ciudad: 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ó tomarlas y, una vez amarradas en la orilla, las hizo quemar en su presencia con gran quebranto de los malvados que perdieron toda esperanza. Esto fue visto por la gente de Casares, Gaucín y Castellar y otros rebeldes de los alfoces de Algeciras, provocando la desilusión y el que se inclinaran a la obediencia enviando sus delegaciones a Abderramán, que aceptó su arrepentimiento, les concedió su perdón y se cuidó, durante su estancia en Algeciras, de traer navíos honrados y dominar el mar.

Sin embargo, la causa que había sido capaz de unir las voluntades de la mayor parte de los habitantes de la serranía se fue debilitando conforme pasaban los años. La conversión de Ben Hafsún al cristianismo hizo que perdiera el apoyo de muchos de sus aliados, que eran enemigos de los omeyas pero fervorosos seguidores de Mahoma. En el año 918 moría Ben Hafsún, recibiendo sepultura, siguiendo el rito cristiano, en la iglesia rupestre de Bobastro. Sus hijos continuarían la lucha hasta el año 928, fecha en la que Abderramán III conquistó la ciudadela y la destruyó. El 16 de enero del año 929, Abderramán III se intituló Califa, dirigente supremo de todo el islam, tanto de Occidente como de Oriente.