For most of its history the Red Sea has joined its two shores rather than separated them, and religions have travelled it in both directions. In the fourth century the Aksumite king Ezana adopted Christianity, brought, according to the tradition, by two shipwrecked Syrian brothers, and Ethiopia became one of the oldest Christian states in the world, its church tied to the Coptic patriarchate of Alexandria until 1959.
The sixth century brought a confrontation across the same water. The kingdom of Himyar in what is now Yemen had adopted Judaism, and in about 523 its king Yusuf attacked the Christian community of Najran, an episode remembered by Christians as a martyrdom and read by some commentators into the Quran's account of the people of the ditch. Aksum invaded across the strait in response, and G. W. Bowersock's study of these wars argues that they set the political and religious stage on which Islam appeared a century later.
Around 615 Muhammad sent a group of his followers across to Aksum for protection, the event Muslim tradition calls the first hijra, and the Christian king who sheltered them is remembered with respect in the sources. Since then the sea has been the pilgrim road: hajjis from Africa crossing to Jeddah, a traffic that built the coral-stone port towns of both coasts and their mosques, and that continues in the air above the same water.