The Gulf of Aden is a young and narrow oceanic basin formed in Oligo-Miocene time between the rifted margins of the Arabian and Somalian plates. Its mean orientation, N75 degrees E, strikes obliquely (50 degrees) to the N25 degrees E opening direction. The western conjugate margins are masked by Oligo-Miocene lavas from the Afar Plume. This paper concerns the eastern margins, where the 19-35 Ma breakup structures are well exposed onshore and within the sediment-starved marine shelf. Those passive margins, about 200 km distant, are non-volcanic. Offshore, during the Encens-Sheba cruise we gathered swath bathymetry, single-channel seismic reflection, gravity and magnetism data, in order to compare the structure of the two conjugate margins and to reconstruct the evolution of the thinned continental crust from rifting to the onset of oceanic spreading. Between the Alula-Fartak and Socotra major fracture zones, two accommodation zones trending N25 degrees E separate the margins into three N110 degrees E-trending segments. The margins are asymmetric: offshore, the northern margin is narrower and steeper than the southern one. Including the onshore domain, the southern rifted margin is about twice the breadth of the northern one. We relate this asymmetry to inherited Jurassic/Cretaceous rifts. The rifting obliquity also influenced the syn-rift structural pattern responsible for the normal faults trending from N70 degrees E to N110 degrees E. The N110 degrees E fault pattern could be explained by the decrease of the influence of rift obliquity towards the central rift, and/or by structural inheritance. The transition between the thinned continental crust and the oceanic crust is characterized by a 40 km wide zone. Our data suggest that its basement is made up of thinned continental crust along the southern margin and of thinned continental crust or exhumed mantle, more or less intruded by magmatic rocks, along the northern margin.