The History of early Islamic Tunisia opens with the arrival of the Arabs who brought their language and the religion of Islam, and its calendar. The Arab conquest followed strategy designed by the Umayyad Caliphate regarding its long-term conflict with the Byzantine Empire. The native Berbers eventually converted to Islam. They might have seen some similarities between themselves and the Arabs, in similar cognate culture, such as familiarity with a pastoral way of life. The first local Islamic ruling house, the Aghlabids, consisted primarily of rule by leading members of this Arab tribe. Fundamental elements of Islamic civilization were established. Although accepting Islam, many Berbers nonetheless resisted rule by the Arabs, establishing the Rustamid kingdom followiing the Kharijite revolt. Next in Ifriqiya (Tunisia) arose the Shia Fatimids, inspired by a few immigrants from the east yet consisting for the most part of Ifriqiya Berbers. The Fatimids later expanded their rule east, through conquest by Berber armies of Egypt, and established their caliphate there which came to include Syria and the Hejaz.
After the initial period of the four rightly-guided caliphs (632-661) following the death of Muhammad (570-632), the ruling family of the Umayyads took firm control of the new Muslim state. The Umayyad Caliphate (661-750) ruled from the city of Damascus; their first Caliph Mu'awiya (602-680, r.661-680) directed Muslim forces in their on-going military contest with the Byzantine Empire. Decades earlier the Byzantine provinces of Syria and Egypt had fallen to Islamic arms. Under Mu'awiya the Umayyad Caliphate could see how the foreign lands west of Egypt figured in the "geo-political" and military strategy of this struggle. Hence there began the decades-long undertaking resulting in the Umayyad conquest of North Africa.