La posición estratégica de la nueva ciudad, fundada en el 712 por Musà ben Nuzayr, puerta de al-Andalus para las tropas musulmanas y los inmigrantes norteafricanos y orientales que comenzaron a llegar a partir de esa fecha, posibilitó el rápido desarrollo de la incipiente medina a lo largo del siglo VIII, aunque el registro arqueológico se muestra muy parco en aportar evidencias materiales, a excepción de algunas monedas. Restos de cimientos y de un muro hallados en la excavación de la calle Gloria, nº 51-55, han sido datados a finales del siglo IX.

Se detecta, por tanto, un escaso nivel de urbanización en los dos primeros siglos de presencia musulmana en la ciudad, aunque las fuentes escritas revelan la existencia de un cierto desarrollo de la población y del comercio en la zona. A la mezquita de las Banderas, fundada por Musà, vino a sumarse, en tiempos de Abderrahmán I, la construcción de la mezquita aljama o principal de la ciudad. En el año 740 está documentada la presencia de un gobernador y de un cadí o juez –uno de los principales agentes de islamización– a finales del siglo VIII o principios del IX, lo que permite afirmar que el proceso de formación de la medina algecireña –y de los elementos que la vinculaban a las fuerzas sociales y políticas dominantes– se fue configurando, aunque débilmente, muy pronto para constituir, a mediados del siglo VIII, la capital de una de las coras o provincias del nuevo Estado y en el puerto de enlace por excelencia con el Norte de África.

Sin embargo desconocemos el nivel de urbanización y la existencia de un posible recinto defensivo en esos primeros tiempos de al-Yazira al-Jadrá. No obstante, esa misma precocidad en la formación de la medina yazirí que ejercía de cabecera de la cora meridional de al-Andalus, su favorable situación geoestratégica y el carácter multiétnico de la población (constituida por clanes árabes y sirios y grupos tribales bereberes, además de los cristianos nativos) serían, a la postre, los elementos desestabilizadores de la provincia y de la propia ciudad.

De la compleja evolución histórica de Algeciras durante el emirato omeya sólo se hará hincapié en dos acontecimientos de especial relevancia: el ataque de los normandos, a mediados del siglo IX, y la participación de la ciudad y de algunos de sus distritos en la rebelión de Omar ben Hafsún contra el poder central.

En el año 859, una flota formada por sesenta bajeles, que procedía de la isla de Thanet y venía mandada por un jefe vikingo de nombre Hastein, arribó a la bahía de Algeciras después de haber mantenido un encuentro cerca de la costa del Algarve con la escuadra musulmana. Según Ibn ‘Idari (siglo XIV), se apoderaron de la ciudad e incendiaron la mezquita aljama. Ibn al-Atir (Siglo XII) añade que, antes de entrar en la ciudad, acamparon alrededor de ella para, desde allí, entablar la batalla. Al-Himyarí (siglo XV) –siguiendo a al-Idrisi– (siglo XII) asegura que la Mezquita de las Banderas de Algeciras recibió ese nombre porque los normandos colocaron en ella sus enseñas cuando asaltaron la ciudad. Añade este compilador que los bastidores de una de las puertas de la citada mezquita se hicieron con la madera de los barcos normandos capturados. Según la Crónica General de España, los vikingos combatieronla tres días, et prisieronla, et quemaronla, et levaron grant aver. Es posible que los habitantes de la ciudad que lograron escapar del asalto se resguardaran en los montes cercanos y que, tres días más tarde, apoyados por los soldados del chund que estaban establecidos en la vecina región de la Janda, lograran contraatacar y expulsar a los invasores infringiéndoles la pérdida de algunos de sus bajeles. Lo cierto es que el éxito del asalto vikingo a Algeciras demuestra la debilidad de las estructuras defensivas de la ciudad a mediados del siglo IX, así como la escasez de fuerzas existentes en la zona para poder defender un puerto de tanta importancia estratégica para el emirato. No cabe duda de que estas incursiones piráticas debieron incluir decisivamente en la creación de una escuadra que vigilara las costas atlánticas de al-Andalus. En este sentido, refiere Ibn al-Kardabus (Siglo XII) que durante el emirato de Muhammad I (852-856) se construyeron 600 navíos de guerra. También se llevaron a cabo las obras de construcción de murallas en las ciudades portuarias que habían sido objeto del saqueo normando como Sevilla y Algeciras. Según Ibn Hayyán (Siglo XI), las murallas de Algeciras fueron edificadas (o reconstruidas) durante el emirato de Muhammad I. Además de edificarse el recinto defensivo, la ciudad fue reconstruida y se la dotó de un puerto militar para que fuese, junto con Almería, arsenal y base de la flota del mediterráneo.

Territorios que estuvieron bajo el control de Omar ben Hafsún hasta el año 914.

En lo que se refiere a la participación de la ciudad y de algunos castillos del interior de la cora en la rebelión de Omar Ben Hafsún, es necesario decir que la posición geográfica de Algeciras, como cabeza de puente en las comunicaciones con el Norte de África, no pasó desapercibida para el rebelde de Bobastro que mantenía intensas relaciones con los fatimíes establecidos en Túnez –enemigos de los Omeyas– y con los príncipes norteafricanos aliados de estos. La estratégica ciudad y su puerto pasaron definitivamente a estar bajo el control de los emires de Córdoba en el año 914.

El 5 de mayo de ese año partió Abderrahmán III con un numeroso ejército mandado por el general Badr ben Ahmad en dirección al Estrecho. Marchó durante varias jornadas hasta llegar a los territorios que dominaba Ben Hafsún en sus entornos, dirigiéndose al valle del Guadiaro donde atacó la fortaleza de Lawra (probablemente Castellar) saqueándola sin hallar oposición. Desde Lawra el ejército se encaminó hacia la capital de la cora, Algeciras, entrando en ella el todavía emir sin resistencia el día 1 de junio. Según Ibn Hayyán, después de haber ocupado Algeciras, el emir hizo traer naves con tripulaciones honradas desde Málaga, Sevilla y otras ciudades leales y las apostó en su puerto con todo tipo de armas y pertrechos, dotándolas de fuego griego. Las hizo tripular por marinos expertos y les ordenó patrullar toda la costa desde Algeciras a Tudmir (Murcia), cortando todo suministro marítimo a Ben Hafsún y los suyos, para que únicamente navegasen los navíos de gente leal. Desde entonces dominó y controló el Estrecho y estuvo a salvo de daño por parte de las embarcaciones que lo atravesaban, haciéndose así con toda la costa y sus fortalezas.