In the 400s CE, the Western Roman Empire fell to East Germanic barbarian tribes such as the Vandals.
Prior to its fall, the Mediterranean Sea was basically a Roman lake, ruled by the Roman empire and with elites at least, and realistically, pretty much everyone, speaking some form of Latin. This included not just the Southern European coast, but the islands of the Aegean sea, Anatolia, the Levant and the North African coast. At its greatest extent, the Roman Empire also extended to include much of Southern Europe (as far north of Southern Britain). The North African province of the Roman Empire was called Africa and that is where the continent got its modern English name.
Prior to the Roman conquest of North Africa, which was a bread belt of the Roman Empire in antiquity, North Africa was inhabited by city states established and ruled by the pre-Hebrew, Semitic maritime peoples known as the Phoenicians and the closely related Punic people of Carthage (roughly speaking in modern Tunisia). Prior to that, and further inland, in lands that the Romans never conquered and weren't really bothered to because it wasn't suitable for Roman style agriculture, were the Berber peoples.
We know from the journal entries of Saint Augustine of Hippo, who died in his 70s in the immediate wake of the Vandal conquest of his North African city, that even before the Vandals conquered this Roman territory, a North African dialect of Latin had been developing.
We also know that while the Vandals took political control of the Northwest African coast of the Mediterranean, that post-conquest the Vandals came to speak the African Latin dialect of the people they conquered, even in official legal documents, rather than converting the people that they ruled to the East Germanic language of the Vandals.
But in the post-Roman Empire era of barbarian rule, North Africa's dialect of African Latin, like that of the other regions of Rome, in which Latin derived Romance languages arose, developed its own regional distinctiveness. The distinction between the letters b and v broke down in favor of using b across the board. The distinction between long and short vowels present in Roman Latin broke down. Consonants at the end of Roman suffix inflections and sometimes the suffixes entirely were dropped. African Latin remained distinct even after a brief reconquest by the Byzantines. The Byzantines were the successors to the Eastern Roman Empire who also failed to replace the local language of North Africa with the Greek language spoken in the Eastern Roman Empire continuously since the Roman Empire conquered it.
While this conclusion is more speculative, African Latin's distinctive features may owe something to a Phoenician/Punic substrate in first generation North African language learners as they began to speak Latin, and from language contact with Berber peoples.
Roughly four hundred years after the fall of the Roman empire in North Africa, Rome's successors were displaced by an expanding Islamic Empire, with lower Egypt and the Northeast Africa falling to it under the the Rashidun Caliphate (632–661), and Northwest Africa and Iberia falling to it completely by 711 CE, under the Umayyad Caliphate (661–750), commencing the Moorish Spain era. Islamic rulers would continue to rule parts of Iberian until 1492 when the Reconquista of Christian Europeans that pushed relentlessly to the South was finally completed and went no further.
In the Middle East, in what is now Iran, in lower Egypt and in Northeast Africa, the Umayyad Caliphate was succeeded by the the Abbasid Caliphate in 750 CE whose capitol was Baghdad which endured in some form until 1258 CE, including the period of the Crusades, and was mostly succeeded by the Malmuk Caliphate based in Cairo commencing in 1261 CE, after a brief interregnum.