Figure 1: The Afar triple junction. The red arrows show the movement of the African, Arabian and Somalian plates away from the Afar depression.
The Red Sea and the Gulf of Aden were formed as the Arabian plate separated from Nubia, as Nubia obliquely collided with the Eurasian plate (Figure 1). NE-directed extension between 35-27million years ago lead to the continents rifting apart and the formation of new oceans along the line of the Red Sea and Gulf of Aden. At the same time as this, between about 31-29Ma, there was a massive eruption of lava - flood basalts - covering some 600,000km2 of the region. Along the margins of the Red Sea these lavas are up to 2000m thick. Sea floor spreading in the Gulf of Aden begun about 16Ma and about 4Ma in the Red Sea.
With the East African Rift System, the Red Sea and the Gulf of Aden form the Afar triple junction. The Red Sea runs roughly straight for 2000km northwards to where it joins the Aqaba-Dead Sea transform rift system (where the plates are sliding past each other). The Gulf of Aden is straight near the triple junction, before curving round to link in the with mid-ocean ridge system in the Indian Ocean (Figure 2).
Figure 2: Regional plate tectonic setting. Red arrows show approximate direction of opening of the rift systems.
Across both the Gulf of Aden mid-ocean ridge system and the southernmost part of the Red Sea the plates are moving not only apart but also sliding past each other with one side moving to the left with respect to the other.
For references used, please see technical version.