We present a new model of P-velocity anomalies in the upper mantle beneath the Arabian Peninsula, Red Sea, and surrounding regions. This model was computed with the use of travel time data from the global catalogue of the International Seismological Center (ISC) for the years of 1980–2011. The reliability of the model was tested with several synthetic tests. In the resulting seismic model, the Red Sea is clearly associated with a higher P-velocity anomaly in the upper mantle at least down to 300 km depth. This anomaly might be caused by upward deviation of the main mantle interfaces caused by extension and thinning of the lithosphere due to passive rifting. Thick lithosphere of the Arabian Platform is imaged as a high-velocity anomaly down to 200–250 km depth. Below this plate, we observe a low-velocity structure that is interpreted as a hot mantle upwelling. Based on the tomography results, we propose that this upper mantle anomaly may represent hot material that migrates westward and play a major role in the formation of Cenozoic basaltic lava fields in western Arabia. On the northeastern side of the Arabian Plate, we clearly observe a dipping high-velocity zone beneath Zagros and Makran, which is interpreted as a trace of subduction or delamination of the Arabian Plate lithosphere.