The history of Western Sahara can be traced back to the times of Carthaginian explorer Hanno the Navigator in the 5th century BC. Though few historical records are left from that period, Western Sahara's modern history has its roots linked to some nomadic groups (living under Berber tribal rule and in contact with the Roman Empire) such as the Sanhaja group, and the introduction of Islam and the Arabic language at the end of the 8th century AD.
Western Sahara has never been a nation in the modern sense of the word. It was home to Phoenician colonies, but those disappeared with virtually no trace. Islam arrived there in the 8th century, but the region, beset with desertification, remained little developed. From the 11th to the 19th centuries, Western Sahara was one of the links between the Sub-Saharan and North African regions. During the 11th century, the Sanhaja tribal confederation allied with the Lamtuna tribe to found the Almoravid dynasty. The conquests of the Almoravids extended over present-day Morocco, Western Algeria, and the Iberian peninsula to the north and Mauritania and Mali to the south, reaching the Ghana Empire. By the 16th century, the Arab Saadi dynasty conquered the Songhai Empire based on the Niger River. Some Trans-Saharan trade routes also traversed Western Sahara.