Many important members of the early Church were from Africa, including Mark the Evangelist, Origen, Tertullian, Saint Augustine of Hippo (from Hippo Regius in what is now Annaba, Algeria) and Clement of Alexandria. Churches in eastern North Africa, such as those in Egypt and Ethiopia, tended to align with the practice of the Eastern Church, but those to the West (the area now known as the Maghreb) were connected to the Roman Church. Three early popes were from the Roman Africa Province. These were Pope Victor I (reigned c . 189 to 199), Pope Miltiades (reigned 311 to 314) and Pope Gelasius I (492 to 496) and all of them were Christian Berbers.
The conventional historical view is that the conquest of North Africa by the Islamic Umayyad Caliphate between AD 647–709 effectively ended Catholicism in Africa for several centuries. A prevailing view is that the Catholic 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 the Coptic Church of Egypt, which is credited as a factor that allowed Coptic Church to remain the majority faith in that country until around after the 14th century.
However, new scholarship has appeared that disputes this. There are reports that the Catholic faith persisted in the region from Tripolitania (present-day western Libya) to present-day Morocco for several centuries after the completion of the Islamic conquest by 700 A.D. There are currently archaeological excavations in western Libya that are focused on the remains of Christian churches dated from the 10th century. There is also evidence of religious pilgrimages after 850 A.D. to tombs of Catholic saints outside the city of Carthage, and evidence of religious contacts with Christians of Islamic 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 the Holy See in Rome. Jonathan Conant (Staying Roman, Conquest and Identity in Africa and the Mediterranean, 439-700, Cambridge, 2012, pp. 362–370) reviews the evidence. He states that Islam did not become the majority in Tunisia until quite late in the 9th century and the "vast majority until some time in the tenth," (pp. 363–64). Christians tended to live in towns and cities and often spoke
African Latin, "al-Latini al-Afriqi", until "at least the 12th century" (ibid. p. 363). By 1076 there were only two bishops left in Africa. Pope Gregory had to appoint a third in order to bring up the number to three to consecrate a new Bishop of Hippo Regius. The decline of Christianity was hastened in part by the destruction wrote by the invasion of the Banu Hilal, sent by the Fatimids in Cairo to punish the Zaid Sunni Islamic emirs. This resulted in the arabization of Tunisia up till then Berber and Latin speaking. In 1159-1160 many of the remaining Christians were evacuated by the Normans to Sicily.
It does look like local Catholicism came under enormous pressure around the time that the Muslim fundamentalist regimes of the Almohads and Almoravids came into power, and the record shows demands made of the local Christians of Tunis to convert to Islam. We still have reports of Christian inhabitants and a bishop in the city of Kairoun around 1150 A.D. - a significant report, since this city had been founded by Arab muslims around 680 A.D. as their administrative center after their conquest. A letter in the 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 Islamic conquest.
By 1830, when the French came as colonial conquerors to Algeria and Tunis, local Catholicism had been extinguished. The growth of Catholicism in the region after the French conquest was built on European colonizers and settlers, and these immigrants and most of their descendants left when the countries of the region became independent.