Already in pre-Islamic times there was an exchange of people between the East African coast and South Arabia. How were they received, and how were they absorbed (or not absorbed) by the South Arabian population? Were they seen as different? What were the markers of difference? South Arabia for some time was an Ethiopian province in late pre- Islamic times (as is testified by references to Abraha) and by consequence, it was under indirect Byzantine influence. When the Persian Sassanids were called for help against the Ethiopians, South Arabia was caught between the two great political powers of the time, Sassanid Persia and the Byzantine empire with its Ethiopians allies. Ethiopians, as well as Persians, stayed on in southern Arabia well into Islamic times and beyond. In early Islamic time, the Persian population in the Yemen provided not only workers and engineers engaged in mining in South Arabia. Moreover, it seems that the early Islamic intelligentsia in South Arabia to a large extent comprised people of Persian origin. How were theses Persians positioned inside the South Arabian communities of their time? South Arabian inscriptions and Byzantine historiography have to be studied to throw light on the relevant interregional connections and history of this period. Some special attention will also be given to the published specialized literature on early Jewish and Christian minorities in the region; the latter survived merely up to the Middle Ages while the former still have a few descendants today. The Persians’ role in the Yemeni highlands during the first Islamic centuries will be compared with the data derived from the Periplus maris Erythraei to demonstrate and highlight principal changes over time.