The expansion into the peninsula as far as the Red Sea and Indian Ocean put the Somalis in sustained contact with Persian and Arab immigrants who had established a series of settlements along the coast. From the eighth to the tenth centuries, Persian and Arab traders were already engaged in lucrative commerce from enclaves along the Red Sea and Indian Ocean as far south as the coast of present-day Kenya. The most significant enclave was the renowned medieval emporium of Saylac on the Gulf of Aden. In the sixteenth century, Saylac became the principal outlet for trade in coffee, gold, ostrich feathers, civet, and Ethiopian slaves bound for the Middle East, China, and India. Over time Saylac emerged as the center of Muslim culture and learning, famed for its schools and mosques. Eventually it became the capital of the medieval state of Adal, which in the sixteenth century fought off Christian Ethiopian domination of the highlands. Between 1560 and 1660, Ethiopian expeditions repeatedly harried Saylac, which sank into decay. Berbera replaced Saylac as the northern hub of Islamic influence in the Horn of Africa. By the middle of the sixteenth century, Saylac and Berbera had become dependencies of the sharifs of Mocha and in the seventeenth century passed to the Ottoman Turks, who exercised authority over them through locally recruited Somali governors.

The history of commercial and intellectual contact between the inhabitants of the Arabian and Somali coasts may help explain the Somalia's connection with the Prophet Muhammad. Early in the Prophet's ministry, a band of persecuted Muslims had, with the Prophet's encouragement, fled across the Red Sea into the Horn of Africa. There the Muslim's were afforded protection by the Ethiopian negus, or king. Thus, Islam may have been introduced into the Horn of Africa well before the faith took root in its Arabian native soil. The large-scale conversion of the Somalis had to await the arrival in the eleventh, twelfth, and thirteenth centuries of Muslim patriarchs, in particular, the renowned Shaykh Daarood Jabarti and Shaykh Isahaaq, or Isaaq. Daarood married Doombira Dir, the daughter of a local patriarch. Their issue gave rise to the confederacy that forms the largest clan-family (see Glossary) in Somalia, the Daarood. For his part, Shaykh Isaaq founded the numerous Isaaq clan-family in northern Somalia. Along with the clan (see Glossary) system of lineages (see Glossary), the Arabian shaykhs probably introduced into Somalia the patriarchal ethos and patrilineal genealogy typical of Indo-Europeans, and gradually replaced the indigenous Somali social organization, which, like that of many other African societies, may have been matrilineal (see The Segmentary Social Order , ch. 2).

Islam's penetration of the Somali coast, along with the immigration of Arabian elements, inspired a second great population movement reversing the flow of migration from northward to southward. This massive movement, which ultimately took the Somalis to the banks of the Tana River and to the fertile plains of Harear, in Ethiopia, commenced in the thirteenth century and continued to the nineteenth century. At that point, European interlopers appeared on the East African scene, ending Somali migration onto the East African plateau.