Medieval Muslim Algeria was a period of Muslim dominance in Algeria during the Middle Ages, spanning the millennium from the 7th century to the 17th century. 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.
The first Arab military expeditions into the Maghreb, between 642 and 669, resulted in the spread of Islam and migration of Arabs to the Maghreb. These early forays from a base in Egypt occurred under local initiative rather than under orders from the central caliphate. 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.