We determine the lateral variations in seismic velocity of the lithospheric mantle beneath the Gulf of Aden and its margins by inversion of Pn (upper mantle high-frequency compressional P wave) traveltimes. Data for this study were collected by several temporary seismic networks and from the global catalogue. A least-squares tomographic algorithm is used to solve for velocity variations in the mantle lithosphere. In order to separate shallow and deeper structures, we use separate inversions for shorter and longer ray path data. High Pn velocities (8.2–8.4 km/s) are observed in the uppermost mantle beneath Yemen that may be related to the presence of magmatic underplating of the volcanic margins of Aden and the Red Sea. Zones of low velocity (7.7 km/s) are present in the shallow upper mantle beneath Sana’a, Aden, Afar, and along the Gulf of Aden that are likely related to melt transport through the lithosphere feeding active volcanism. Deeper within the upper mantle, beneath the Oman margin, a low-velocity zone (7.8 km/s) suggests a deep zone of melt accumulation. Our results provide evidence that the asthenosphere undergoes channelized flow from the Afar hotspot toward the east along the Aden and Sheba Ridges.