In Cairo the Fatimid caliph reacted by inviting the Bani Hilal and Bani Salim, beduin tribes from Arabia known collectively as the Hilalians, to migrate to the Maghrib and punish his rebellious vassals, the Zirids. The Arab nomads spread across the region, in the words of the historian Ibn Khaldun, like a "swarm of locusts," impoverishing it, destroying towns, and dramatically altering the face and culture of the countryside.

The Hilalian impact on Cyrenaica and Tripolitania was devastating in both economic and demographic terms. Tripoli was sacked, and what little remained of urban life in once-great cities like Cyrene was snuffed out, leaving only ruins. Over a long period of time, Arabs displaced Berbers (many of whom joined the Hilalians) from their traditional lands and converted farmland to pasturage. Land was neglected, and the steppe was allowed to intrude into the coastal plain.

The number of Hilalians who moved westward out of Egypt has been estimated as high as 200,000 families. The Bani Salim seem to have stopped in Libya, while the Bani Hilal continued across the Maghrib until they reached the Atlantic coast of Morocco and completed the Arabization of the region, imposing their social organization, values, and language on it. The process was particularly thorough in Cyrenaica, which is said to be more Arab than any place in the Arab world except for the interior of Arabia.

The Norman rulers of southern Italy took advantage of the Zirids' distress in North Africa to invade Sicily in 1060 and bring it back under Christian control. By 1150 the Normans held a string of ports and fortresses along the coast between Tunis and Tripoli, but their interests in North Africa were commercial rather than political, and no effort was made to extend the conquest inland.

Data as of 1987