The conventional historical view is that the conquest of North Africa by the Islamic Umayyad Caliphate between AD 647 and 709 effectively ended Catholicism in Africa for several centuries. The prevailing view is that the Church at that time lacked the backbone of a monastic tradition and was still suffering from the aftermath of heresies including the so-called Donatist heresy, and this contributed to the earlier obliteration of the Church in the present day Maghreb. Some historians contrast this with the strong monastic tradition in Coptic Egypt, which is credited as a factor that allowed the Coptic Church to remain the majority faith in that country until around after the 14th century AD.

However, new scholarship has appeared that disputes this. There are reports that the Roman Catholic faith persisted in the region from Tripolitania (present-day western Libya) to present-day Morocco for several centuries after the completion of the Arab conquest by 700 AD. A Christian community is recorded in 1114 in Qal'a in central Algeria. There is also evidence of religious pilgrimages after 850 AD to tombs of Catholic saints outside of the city of Carthage, and evidence of religious contacts with Christians of Muslim Spain. In addition, calendar reforms adopted in Europe at this time were disseminated amongst the indigenous Christians of Tunis, which would have not been possible had there been an absence of contact with Rome.

Local Catholicism came under pressure when the Muslim fundamentalist regimes of the Almohads and Almoravids came into power, and the record shows demands made that the local Christians of Tunis to convert to Islam. There are reports of Christian inhabitants and a bishop in the city of Kairouan around 1150 AD - a significant report, since this city was founded by Arab Muslims around 680 AD as their administrative center after their conquest. A letter in Catholic Church archives from the 14th century shows that there were still four bishoprics left in North Africa, admittedly a sharp decline from the over four hundred bishoprics in existence at the time of the Arab conquest. Berber Christians continued to live in Tunis and Nefzaoua in the south of Tunisia up until the early 15th century, and the first quarter of the 15th century, the native Christians of Tunis, though much assimilated, extended their church, perhaps because the last Christians from all over the Maghreb had gathered there.