Когда Ибн Бишр подавил восстание Майсары-бедняка, не получив помощи от Абд аль-Малика, он приказал построить лодки, нагрузить их оружием и снаряжением, верховыми и вьючными конями и на этих лодках переправился на андалусский берег. Узнав об этом, Абд аль-Малик аль-Фихри собрал войска и встретил Ибн Бишра у Альхесираса, где между ними произошло крупное сражение, и аль-Фихри был в нем разбит. Балдж гнал Абд аль-Малика до самой Кордовы, и между ними произошли восемнадцать сражений, и все они кончались для аль-Фихри неудачей, так что в конце концов Балдж вошел в Кордову и, взяв аль-Фихри в плен, повелел распять его у входа на мост через долину Кордовы, где позже была построена мечеть...

А в это время Абд ар-Рахман ибн Алькама аль-Лахми, которого Абд аль-Малик назначил наместником Арагона, узнав о постигшей аль-Фихри участи, собрал войска и двинулся против Балджа, чтобы отомстить за смерть аль-Фихри. Его поддержало множество андалусских арабов и берберов, и все они отправились на Кордову. Балдж вышел против них во главе десяти тысяч сирийцев и людей из рода Бану Умайя, а у Абд ар-Рахмана ибн Алькамы было сорок тысяч. Между ними произошло кровопролитное сражение близ селения Аква-Портора в округе Уэльвы. На закате бой кончился, и обнаружилось, что из людей Ибн Алькамы убито десять тысяч, а из воинов Балджа — всего тысяча. Тогда Ибн Алькама сказал: “Покажите мне этого Балджа”. А надо сказать, что Ибн Алькама был одним из самых метких стрелков своего времени. Когда на следующее утро снова началось сражение, ему показали Балджа, и он выпустил в него стрелу, которая, попав в рукав кольчуги, пригвоздила руку Балджа к телу, и Ибн Алькама воскликнул: “Ну вот я и попал в этого Балджа”. К вечеру бой стих и Валдж умер от этой раны. .Однако сирийцы не покинули Кордову,— их предводителем стал Салаба ибн Салама аль-Амили, а Ибн Алькаме пришлось вернуться на границу.

Между тем арабы и берберы Андалусии не переставали воевать с пришельцами, сирийцами и Омайядами, говоря им: “Нам самим мало места в этой стране, уходите отсюда!” Узнав о смуте, раздирающей Андалусию, халиф Хишам ибн Абд аль-Малик, посоветовавшись с верными людьми, решил прибегнуть к помощи людей из Бану Мудар и назначил правителем Андалусии Абу-ль-Хаттара аль-Кальби, вручив ему грамоту на правление и знамя.