In this study we present a 3D P-wave upper-mantle tomography model of the SW Iberian margin and Alboran Sea based on teleseismic arrival times recorded by Iberian and Moroccan land stations and by a seafloor network deployed for 1 year in the Gulf of Cadiz area during the EC-NEAREST project. The 3D model was computed down to 600 km depth. The tomographic images exhibit significant velocity contrasts, as large as 3%, confirming the complex evolution of this plate boundary region. Prominent high-velocity anomalies are found beneath Betics-Alboran Sea, off-shore SW Portugal, and N Portugal, at sublithospheric depths. The transition zones between high and low velocity anomalies in SW and S Iberia are associated to the contact of oceanic and continental lithosphere. The fast structure below the Alboran Sea-Granada area depicts a L-shaped body steeply dipping from the uppermost mantle to the transition zone where it becomes less curved. This anomaly is consistent with the results of previous tomographic investigations and recent geophysical data such as stress distribution, GPS measurements of plate motion, and anisotropy patterns. In the Atlantic domain, under the Horseshoe Abyssal Plain, the main feature is a high-velocity zone found at uppermost mantle depths. This feature appears laterally separated from the positive anomaly recovered in the Alboran domain by the interposition of low-velocity zones which characterize the lithosphere beneath the SW Iberian peninsula margin, suggesting that there is no continuity between the high velocity anomalies of the two domains west and east of the Gibraltar Strait.