Fired up by Kharijite puritan preachers, the Berber revolt against their Umayyad Arab rulers began in Tangier in 740, and was led initially by Maysara al-Matghari.

After failing to capture the Umayyad provincial capital of Kairouan, the Berber rebel armies dissolved, and the western Maghreb fragmented into a series of small statelets, ruled by tribal chieftains and Kharijite imams.

From the early days of the Muslim conquest of North Africa, Arab commanders had treated non-Arab (notably Berber) auxiliaries inconsistently, and often rather shabbily.

In 718, the Umayyad caliph Umar II finally forbade the levying of extraordinary taxation and slave tributes from non-Arab Muslims, defusing much of the tension.

As a result, resentful Berbers grew receptive to radical Kharijite activists from the east (notably of Sufrite and later Ibadite persuasion) which had begun arriving in the Maghreb in the 720s.

Coming in after a period of mismanagement, Ubayd Allah soon set about expanding the fiscal resources of the government by leaning heavily on the non-Arab populations, resuming the extraordinary taxation and slave-tribute without apologies.

Inspired by the Sufrite preachers, the North African Berber tribes of western Morocco – initially, the Ghomara, Berghwata and Miknasa – decided to break openly into revolt against their Arab overlords.

The opportunity arose sometime in early 740 (122 AH), when the powerful Ifriqiyan general Habib ibn Abi Ubayda al-Fihri, who had recently been imposing his authority on the Sous valley of southern Morocco, received instructions from the Kairouan governor Ubayd Allah to lead a large expedition across the sea against Byzantine Sicily.

As soon as the mighty Habib was safely gone, Maysara assembled his coalition of Berber armies, heads shaven in the Sufri Kharijite fashion and with Qura'nic inscriptures tied to their lances and spears, and brought them bearing down on Tangiers.

He immediately dispatched messengers to his general Habib ibn Abi Obeida al-Fihri in Sicily instructing him to break off the expedition and urgently ship the Ifriqiyan army back to Africa.

The Arab cavalry commander Khalid ibn Abi Habiba did not give pursuit, but just held his line south of Tangier, blockading the Berber-held city, while awaiting the reinforcements from Habib's Sicilian expedition.

Seeing Sufrite preachers everywhere in the city, the Umayyad commander ordered his nervous Arab troops to conduct a series of round-ups in Tlemcen, several of which ended in indiscriminate massacres.

There, Habib encountered Musa ibn Abi Khalid, an Umayyad captain who had bravely stayed behind in the vicinity of Tlemcen gathering what loyal forces he could find.

The state of panic and confusion was such that Habib ibn Abi Obeida decided to blame the guiltless captain for the entire mess and cut off one of his hands and one of his legs in punishment.

[citation needed] The ancient and deep pre-Islamic tribal rivalry between Qaysid and Yemenite found itself invoked in repeated quarrels between the earlier colonists and the arriving junds.)

Collecting the Syrian vanguard, Kulthum hurried along to make junction with the remaining Ifriqiyan forces (some 40,000) of Habib ibn Abi Obeida al-Fihri holding ground in the vicinity of Tlemcen.

The Berber rebel army, under the leadership of Khalid ibn Hamid al-Zanati (perhaps jointly with a certain Salim Abu Yusuf al-Azdi [12]), while boasting great numbers (some 200,000), were very poorly equipped.

The Zenata Berber leader Khalid ibn Hamid al-Zanati who delivered the two great victories over the Arab armies disappears from the chronicles shortly after Bagdoura (741).

The most immediate threat arose in southern Ifriqiya, where the Sufrite leader Uqasha ibn Ayub al-Fezari raised a Berber army and laid sieges to Gabès and Gafsa.

By a rapid sally south with the remnant of the Ifriqiyan army, the Kairouan qadi Abd al-Rahman ibn Oqba al-Ghaffari managed to defeat and disperse Uqasha's forces near Gafsa in December, 741.

[15] But the qadi possessed far too few Arab troops to put up a pursuit, and Uqasha immediately set about re-assembling his forces quietly around Tobna in the Zab valley of western Ifriqiya.

Immediately after hearing of the disaster at Bagdoura, the Caliph Hisham ordered the Umayyad governor of Egypt, Handhala ibn Safwan al-Kalbi, to quickly take charge of Ifriqiya.

Although Kairouan was saved for the caliphate, and with it the core of Ifriqiya, Handhala ibn Safwan now faced the unenviable task of dragging the more westerly provinces, still under Berber sway, back into the fold.

With the frontier garrisons in the northwest suddenly evacuated, the Christian king Alfonso I of Asturias could hardly believe his luck, and set about dispatching Asturian troops to seize the empty forts.

These trapped Berber communities were called "Maragatos" by the local Christian Leonese (etymology uncertain, possibly from mauri capti, "captive Moors").

But news soon reached the Andalusian governor that the Berber rebel armies from the northwest had been organized and were now barreling south in three columns, towards Toledo, Córdoba and Algeciras.

In a carefully negotiated treaty, Abd al-Malik granted the Syrians permission to cross over, on the condition that they promise to return to North Africa within a year of the settlement of the Berber matter in Al-Andalus.

The Syrian junds under Balj ibn Bishr crossed the straits in early 742 and immediately headed to the environs of Medina-Sidonia, where they intercepted and disposed of the Berber column aiming for Algeciras.

The Syrians delivered a decisive defeat upon the Andalusian at the Battle of Aqua Portora outside of Córdoba in August 742, but Balj ibn Bishr was mortally wounded in the field.

Abu al-Khattar arrived in May 743 and immediately set about restoring peace in Al-Andalus, liberating prisoners (Arab and Berber) and figuring a resolution to the displaced Syrian troops.