This region has, since prehistory, been both isolated by the Sahara and Libyan deserts and linked into the vast movement of people around the Mediterranean. Thus, it has its own cultural character but has exchanged many genes with its neighbors. From the beginning of the study period until the high Middle Ages, the majority of the population has consisted of Berbers, speakers of a group of languages distantly akin to Semitic tongues and Ancient Egyptian. Since before the beginning of the study period, however, they were ruled by a Roman upper crust. Indeed, if your ancestors were in the Maghrib in 500 CE, their ancestors might also have lived anywhere within the Roman Empire in 1 CE..
Trans-Saharan slave trade: Starting near the beginning of the study period, camels were introduced to the Sahara and trans-Saharan trade became common and reliable, with merchants from the Maghrib trading with partners in the empires of the Niger River valley (Ghana, later Mali and Songhay). The typical trade was of Mediterranean manufactured goods for slaves from the nations of West Africa - sort of a "series-pilot" for the later transatlantic slave trade. Thus, if your ancestors were in the Maghrib in 500 CE, their ancestors might also have lived in the Niger River valley or the nations to the south of it in 1 CE. (This infusion of West African genes remains a constant fixture of Maghribi demographics until after 1490, when the West Africa began selling its captives into the European-controlled transatlantic slave trade. )
Fifth Century: The migrations of central and northern European peoples that engulfed the western Roman Empire made it to the Maghrib with the invasion of the Vandals, who replaced the Romans as the new aristocracy. The Vandals originated in southern Sweden during the first century and migrated through modern Poland, Czech Republic, Slovakia, Austria, Southern Germany, France, and Spain, eventually to land in North Africa. Thus, if your ancestors were in the Maghrib in 500 CE, their ancestors might also have lived anywhere along the track of the Vandalic migrations in 1 CE.
Seventh century: The new Islamic state expanded to include the Maghrib (Arabic for "the West"). Like the Romans previously, the Vandals lost power, intermarried, and ceased to exist as a separate group. Now the upper crust was Arab. The conversion of the Berbers to Islam gave them a common purpose and increased security for the rapidly expanding Trans-Saharan commerce. Also, it was mostly a Berber army that Tariq ibn Ziyad led to its amazing victory in Spain. Thus, if your ancestors were in the Maghrib in 1000 CE, some of their ancestors just barely might also have lived in Arabia in 500 CE. Note, however:
Twelfth century: The ultimate collision between the independent Maghrib and central Islamic authorities came when the Shiite Fatimid caliphs (based in Egypt) decided to assert control over the undisciplined west. A major piece of their strategy was to encourage Arabic-speaking Bedouin nomads from Egypt, the Banu Hilal and Banu Sulaym to settle in the Maghrib. This was the first major infusion of Arab genes to the region. Thus, if your ancestors were Arabic speakers in the Maghrib in 1490 CE, some of their ancestors surely also have lived in Egypt and Arabia in 100000 CE.
Spanish reconquest and resurgence
Sixteenth century: In 1492, the unified kingdoms of Castille and Aragon eliminated Granada, the last Islamic state in Iberia and instituted the mass-deportation of Spanish Muslims and Jews. Whether your ancestors were Muslims or Jews, if they lived in the Maghrib in 1800, they might trace at least part of their ancestry back to this infusion of Spanish genes at the end of the fifteenth century.
But that's not all. At this point, Portuguese merchants established direct contact with the city-states of Western sub-Saharan Africa. From this point forward, traffic in West African slaves moved across the Atlantic to Europe or the New World, rather than across the Sahara to the Maghrib. To make matters worse, competition for military dominance of the Western Mediterranean between Spain and the Ottoman Empire led to a breakdown of commerce. Except for the introduction of a super-thin upper crust of Ottoman officials, the Maghrib was more isolated than at any time previously. In place of proper trade, the Maghrib became the haunt of "corsairs" - pirates preying on the shipping of Christian nations. These received the attention of the young US Navy under president Jefferson, ("...to the shores of Tripoli...") but more notoriously, they served as a pretext for attack by....
1830 - France: Under the pretext of suppressing Algerian corsairs, France invaded. The French were fought bitterly, resulting in the deployment of a very large French fighting force and the depopulation of the countryside. The consequence was a movement toward widespread permanent French settlement. Resistance to French colonization led to a century of constant bitter hostility. Not a climate for romance. Nevertheless, if your ancestry is Algerian and your family folklore indicates French connections, or vice versa, Take it seriously.