Aplastada la rebelión bereber de Al-Andalus por encargo del gobernador Abd al-Malik ibn Qatán, los sirios de Balch exigieron a éste su traslado a Africa en los términos pactados. Pero a éste le era imposible cumplir con su parte del trato de transportarles a todos juntos, por falta de suficientes barcos y porque los sirios habían aumentado su impedimenta gracias al botín conseguido de los bereberes. Por este motivo, los sirios se dirigieron a Córdoba, hicieron prisionero a Abd al-Malik y proclamaron gobernador a su jefe Balch. Las fuentes árabes fechan este hecho en septiembre de 741.

Para desgracia de Abd al-Malik, el gobernador de Algeciras había descuidado la atención de los rehenes sirios y como consecuencia murió uno de ellos, un noble de Siria. Las tropas pidieron la cabeza de Abd al-Malik, alegando que la muerte del rehén se había debido a un descuido imperdonable. Entonces los kalbíes yemeníes del ejército sirio acusaron a Balch de estar protegiendo a un qaisí. No hay que olvidar que Balch era un noble qaisí de la tribu de Qurayx, y que Abd al-Malik, aunque del partido medinés, era también qaisí de la tribu Mudhar. Ante la acusación y para evitar peleas en el ejército sirio, Balch les entregó al prisionero.

Abd al-Malik fue crucificado entre un cerdo y un perro. Su cadáver fue robado por sus libertos bereberes de Almodovar. El paraje de su muerte tomó el nombre de Maslib (lugar de la crucifixión) de Abd al-Malik, nombre que conservó hasta que su hijo Umayya construyó una mezquita en tiempos del valí Yusuf al-Fihri. La mezquita, conocida como Mezquita Umayya, fue destruida años después, el dia de la sublevación de los cordobeses contra el emir Al-Hakam I, quedando el sitio abandonado y olvidados sus nombres.

Entretanto, los hijos de Abd al Malik, Qatan y Umayya, huyeron a Mérida y Zaragoza, desde donde comenzaron a planear su venganza. Reunieron un ejército en la region de Narbona y marcharon contra Córdoba, siendo derrotados en la batalla de Aqua Portora, a resultas de la cual murió el recientemente proclamado gobernador Balch.