Mantle plumes and consequent plate extension have been invoked as the likely cause of East African Rift volcanism. However, the nature of mantle upwelling is debated, with proposed configurations ranging from a single broad plume connected to the large low-shear-velocity province beneath Southern Africa, the so-called African Superplume, to multiple lower-mantle sources along the rift. We present a new P-wave travel-time tomography model below the northern East-African, Red Sea and Gulf of Aden rifts and surrounding areas. Data are from stations that span an area from Madagascar to Saudi Arabia. The aperture of the integrated dataset allows us to image structures of ∼100 km length scale down to depths of 700-800 km beneath the study region. Our images provide evidence of two clusters of low-velocity structures consisting of features with diameter of 100-200 km that extend through the transition zone, the first beneath Afar and a second just west of the Main Ethiopian Rift, a region with off-rift volcanism. Considering seismic sensitivity to temperature, we interpret these features as upwellings with excess temperatures of 100±50 K. The scale of the upwellings is smaller than expected for lower mantle plume sources. This, together with the change in pattern of the low-velocity anomalies across the base of the transition zone, suggests that ponding or flow of deep-plume material below the transition zone may be spawning these upper-mantle upwellings.