Magnetic and gravity data gathered during the Encens-Sheba cruise (2000 June) in the eastern Gulf of Aden provide insights on the structural evolution of segmentation from rifted margins to incipient seafloor spreading. In this study, we document the conjugate margins asymmetry, confirm the location of the ocean-continent transition (OCT) previously proposed by seismic data, and describe its deep structure and segmentation. In the OCT, gravity models indicate highly thinned crust while magnetic data indicate presence of non-oceanic high-amplitude magnetic anomalies where syn-rift sediments are not observed. Thus, the OCT could be made of ultra-stretched continental crust intruded by magmatic bodies. However, locally in the north, the nature of the OCT could be either an area of ultra-slow spreading oceanic crust or exhumed serpentinized mantle. Between the Alula-Fartak and Socotra fracture zones, the non-volcanic margins and the OCT are segmented by two N027 degrees E-trending transfer fault zones. These transfer zones define three N110 degrees E-trending segments that evolve through time. The first evidence of oceanic spreading corresponds to the magnetic anomaly A5d and is thus dated back to 17.6 Ma at least. Reconstruction of the spreading process suggests a complex non-uniform opening by an arc-like initiation of seafloor spreading in the OCT. The early segmentation appears to be directly related to the continental margin segmentation. The spreading axis segmentation evolved from three segments (17.6 to 10.95 Ma) to two segments (10.95 Ma to present). At the onset of the spreading process, the western segment propagated eastwards, thus reducing the size of the central segment. The presence of a propagator could explain the observed spreading asymmetry with the northern flank of the Sheba ridge being wider than the southern one.