During the early stages in the formation of divergent margins, the lithosphere experiences large changes in temperature that can determine its strength and influence magma generation. This, in turn, may play a key role in continental rifting, break-up, and subsequent subsidence. Here we present surface heat-flow data from the Eastern Gulf of Aden, which is a recently formed divergent margin between Africa and Arabia. In the deeper parts of the margin the heat flow is high and constant, but it decreases abruptly near the shelf-slope. Our numerical models, in conjunction with geophysical and geological constraints, suggest that the data are best explained by a thermal anomaly in the upper mantle that has persisted after continental break-up. We suggest that this anomaly is related to small-scale convection that occurred during and after rifting. Similar anomalies could have characterized other divergent margins: for example, the presence of shallow-water sediments deposited after the opening of the Atlantic Ocean hints at lower subsidence than would have occurred in the absence of persistent thermalanomalies.