Las victorias de los bereberes en Ifriqiya incitó a los de Al-Andalus hicieran lo propio. Además de las posibles causas fiscales y religiosas, en Al-Andalus se añadía el asunto del reparto de las tierras. En efecto, los árabes de Muza se habían reservado las ricas vegas del centro, Levante y Andalucía, y dieron a los bereberes de Tariq las áridas mesetas y tierras del Norte, expuestas a los ataques de los cada vez más envalentonados cristianos.

Los bereberes abandonaron sus tierras de Galicia, León y Castilla, excepto Zaragoza, donde eran minoría, matando a los árabes que encontraban a su paso, y derrotaron a las columnas enviadas en su contra por el gobernador Abd al-Malik.

Previamente, tras la derrota del rio Sebu frente a Tánger, la vanguardia siria del ejército árabe se había refugiado en Ceuta, donde fue inmediatamente sitiado. Balch había pedido socorro al gobernador de Al-Andalus, pero éste, como era del partido medinés, no hizo caso al sirio, pensando desquitarse así de la derrota de Harras. Pero la situación provocada por la rebelión bereber en la península se hizo tan insostenible, que Abd al-Malik se vió obligado a tratar con Balch el paso de su ejercito a Al-Andalus a cambio de combatir a los rebeldes. Pactaron que los sirios dejarían en Algeciras diez personas importantes de cada "chund" o división en calidad de rehenes y que, una vez aplastada la rebelión bereber, los desembarcaría a todos juntos en un punto de Ifriqiya donde los bereberes no pudieran molestarles.

Mientras tanto, los bereberes, procedentes de Galicia, Mérida, Astorga, Talavera y Coria, eligieron un jefe y se dividieron en tres columnas dispuestos a atacar Sidonia, Córdoba y Toledo, poniendo cerco a ésta última. Llevaba un mes resistiendo cuando apareció el ejército árabe al mando de Qatan y Umayya, hijos del gobernador Abd al-Malik, y compuesto por los sirios de Balch y baladíes españoles.

Los bereberes, que se habían rasurado la cabeza a imitación de Masayra, caudillo de la rebelión en Africa, a fin de no ocultar la causa que defendían y no confundirse con los contrarios, fueron derrotados con gran mortandaz en el rio Guazalete, cerca de Toledo. También fueron derrotados por los sirios en el rio Guadalete, poniendo fin al cerco de Medina Sidonia. Los sirios, ahitos de botín, se dividieron en varios destacamentos y fueron persiguiendo y matando bereberes por toda la península, terminando de esta forma la rebelión.