We investigate the crustal and upper-mantle shear-velocity structure of Saudi Arabia by fundamental-mode Rayleigh-wave group-velocity tomography and shear-wave velocity inversion. The seismic dataset is compiled using ∼140 stations of the Saudi National Seismic Network (SNSN) operated by the Saudi Geological Survey (SGS). We measure Rayleigh-wave group-velocities at periods of 8–40 s from regional earthquakes. After obtaining 1-D shear-wave velocity models by inverting group-velocities at each grid node, we construct a 3-D shear-velocity model for Saudi Arabia and adjacent regions by interpolating the 1-D models. Our 3-D model indicates significant lateral variations in crustal and lithospheric thickness, as well as in the shear-wave velocity over the study region. In particular, we identify zones of reduced shear-wave speed at crustal levels beneath the Cenozoic volcanic fields in the Arabian Shield. The inferred reductions of 2–5% in shear-wave speed may be interpreted as possibly indicating the presence of partial melts. However, their precise origin we can only speculate about. Our study also reveals an upper-mantle low velocity zone (LVZ) below the Arabian Shield, supporting the model of lateral mantle flow from the Afar plume. Further geophysical experiments are needed to confirm (or refute) the hypothesis that partial melts may exist below the Cenozoic volcanism in western Saudi Arabia, and to build a comprehensive geodynamic–geological model for the evolution and present state of the lithosphere of the Arabian Plate and the Red Sea.