The sixth and seventh centuries constitute an extended period of contested hegemony bridging the more stable Late Roman and Early Islamic eras. The period of Ethiopian hegemony begins with the delegation of the Red Sea frontier by Byzantines to the Aksumites, wherein the Byzantine-backed Aksumsite conquest of Himyarite Yemen is discussed. The period of Persian hegemony spans the Sasanian conquest of Yemen and Egypt, which is located within the wider ‘cold war’ between the Byzantines and Sasanians. The period of Arab hegemony considers the Muslim co-option of post-Himyarite Yemen and conflict with Aksumite Ethiopia, culminating in the Arab conquest of Egypt, in which the Red Sea is shown to have played an important role.