Another group of the Miknasa had taken part in the successful massive Berber Revolt of 739-42, which had managed to wipe out the Umayyad Arab presence in Morocco and Algeria.

The Miknasa had adopted Kharijism-Islam and establish the Emirate of Sijilmasa on the northern edge of the Sahara.

According to al-Bakri's Book of Routes and Places, Sufrite Kharijites first settled the town of Sijilmassa, along the River Ziz in the Tafilalt oasis at the northern edge of the Sahara Desert in present Morocco, in the wake of the Berber revolts against the Umayyads.

The story al-Bakri relates says that others joined these early settlers in residence there, until they numbered around four thousand, at which point they laid the groundwork for the city.

They elected a leader, ‘Isa bin Mazid al-Aswad (the Black), to handle their affairs during the earliest first few years after the town’s establishment.

The Berber peoples of the Maghreb in the early Middle Ages can be roughly classified into three major groups: the Zenata across the north, the Masmuda concentrated in central Morocco, and the Sanhaja, clustered in two areas: the western part of the Sahara and the hills of the eastern Maghreb.

The eastern Sanhaja include the Kutama Berbers, who had been the base of the Fatimid rise in the early tenth century, and the Zirid dynasty, who have ruled Ifriqiya as vassals of the Fatimids since the latter moved to Egypt in 972.

The western Sanhaja are divided into several tribes: the Gazzula and the Lamta in the Draa valley and the foothills of the Anti-Atlas range; further south, encamped in the western Sahara desert, are the Massufa, the Lamtuna and the Banu Warith; and most southerly of all, the Gudala (or Judala), in littoral Mauritania down to the borderlands of the Senegal River.

The western Sanhaja had been converted to Islam some time in the ninth century.

They had been subsequently united in the tenth century and, with the zeal of neophyte converts, had launched several campaigns against the "Sudanese" (pagan peoples of sub-Saharan Africa).

Under their king Tinbarutan ibn Usfayshar, the Sanhaja Lamtuna had erected (or captured) the citadel of Awdaghust, or Aoudaghost, a critical stop on the trans-Saharan trade route.

After the collapse of the Sanhaja union, Awdagust had passed over to the Ghana empire; and the trans-Saharan routes had been taken over by the Zenata Maghrawa of Sijilmassa.

The Maghrawa had also exploited this disunion to dislodge the Sanhaja Gazzula and Lamta out of their pasturelands in the Sous and Draa valleys.

Around 1035, the Lamtuna chieftain Abu Abdallah Muhammad ibn Tifat (alias Tarsina), had tried to reunite the Sanhaja desert tribes, but his reign had lasted less than three years.

The Almoravids’ rigorous application of Islam had soon provoked a revolt in 1055.

Upon the death of Yahya ibn Umar in the spring of 1056 at the Battle of Tabfarilla, Abdallah ibn Yasin appoints Abu Bakr as the new military commander of the Almoravids.

This same year, Abu Bakr recaptures Sijilmassa from the Maghrawa of the Zenata confederation, recapturing the city definitively for the Almoravids in late 1056.