The new faith, in its various forms, would penetrate nearly all segments of society, bringing with it armies, learned men, and fervent mystics; in large part, it would replace tribal practices and loyalties with new social norms and political idioms.
When the seat of the caliphate moved from Medina to Damascus, the Umayyads (a Muslim dynasty ruling from 661 to 750) recognized that the strategic necessity of dominating the Mediterranean dictated a concerted military effort on the North African front.
In 670, therefore, an Arab army under Uqba ibn Nafi established the town of Al-Qayrawan about 160 kilometers south of present-day Tunis and used it as a base for further operations.
Abu al-Muhajir Dinar, Uqba's successor, pushed westward into Algeria and eventually worked out a modus vivendi with Kusaila, the ruler of an extensive confederation of Christian Berbers.
Governors appointed by the Umayyad caliphs ruled from Al Qayrawan, capital of the new wilaya (province) of Ifriqiya, which covered Tripolitania (the western part of present-day Libya), Tunisia, and eastern Algeria.
Although nominally serving at the caliph's pleasure, Al Aghlab and his successors, the Aghlabids, ruled independently until 909, presiding over a court that became a center for learning and culture.
Founded by the Berber general Ziri ibn Manad, the Zirids established their capital in the city of Ashir, located in modern-day Algeria.
[3] The dynasty's early years were marked by political turmoil and conflict with other Muslim powers, but the Zirids eventually emerged as a dominant force in the region, with their influence extending as far as Sicily.
In the closing decades of the 9th century, missionaries of the Ismaili sect of Shia Islam converted the Kutama Berbers of what was later known as the Petite Kabylie region and led them in battle against the Sunni rulers of Ifriqiya.
Ibadi Kharijite refugees from Tahert fled south to the oasis at Ouargla beyond the Atlas Mountains, whence in the 11th century they moved southwest to Oued M'zab.
For many years, the Fatimids posed a threat to Morocco, but their deepest ambition was to rule the East, the Mashriq, which included Egypt and Muslim lands beyond.
This Berber dynasty, which had founded the towns of Miliana, Médéa, and Algiers and centered significant local power in Algeria for the first time, turned over its domain west of Ifriqiya to the Banu Hammad branch of its family.
The Almoravid movement developed early in the 11th century among the Sanhaja confederation, whose control of trans-Saharan trade routes was under pressure from the Zenata Berbers in the north and the state of Ghana in the south.
Yahya Ibn Ibrahim, a leader of the Godala tribe of the Sanhaja confederation, decided to raise the level of Islamic knowledge and practice among his people.
The Almoravid movement shifted from promoting religious reform to engaging in military conquest after 1054 and was led by Lamtuna leaders: first Yahya, then his brother Abu Bakr, and then his cousin Yusuf ibn Tashfin.
Under the Almoravids, the Maghrib and Spain acknowledged the spiritual authority of the Abbasid caliphate in Baghdad, reuniting them temporarily with the Islamic community in the Mashriq.
Abd al Mumin forced the submission of the amirs and reestablished the caliphate of Córdoba, giving the Almohad sultan supreme religious as well as political authority within his domains.
For the first time, the Maghrib was united under a local regime, and although the empire was troubled by conflict on its fringes, handcrafts and agriculture flourished at its center and an efficient bureaucracy filled the tax coffers.
The regime, which depended on the administrative skills of Andalusians, was plagued by frequent rebellions but learned to survive as the vassal of the Marinids or Hafsids or later as an ally of Spain.
Situated at the head of the Imperial Road through the strategic Taza Gap to Marrakech, the city controlled the caravan route to Sijilmasa, gateway for the gold and slave trade with the western Sudan.
In Algeria, the influence of the marabouts continued through much of the Ottoman period, when the authorities would grant political and financial favors to these leaders to prevent tribal uprisings.
The final triumph of the 700-year Christian reconquest of Spain, marked by the fall of Granada in 1492, was accompanied by the forced conversion of Spanish Muslims (Moriscos).
Without much difficulty, Christian Spain imposed its influence on the Maghrib coast by constructing fortified outposts (presidios) and collecting tribute during the 15th and early 16th centuries.
The presidios in North Africa turned out to be a costly and largely ineffective military endeavor that did not guarantee access for Spain's merchant fleet.
Moreover, from the 16th to the 18th century, sailing superior ships and hammering out shrewd concessions, merchants from England, Portugal, the Netherlands, France, and Italy, as well as Spain, dominated Mediterranean trade.
North African rulers engaged in it increasingly in the late 16th and early 17th century because it was so lucrative, and because their merchant vessels, formerly a major source of income, were not permitted to enter European ports.
The taifa also gained prestige and political influence because of its role in fighting the infidel and providing the merchants and rulers of Algiers with a major source of income.