We have constructed a 3-D shear wave velocity (Vs) model for the crust and uppermost mantle beneath the Middle East using Rayleigh wave records obtained from ambient-noise cross-correlations and regional earthquakes. We combined one decade of data collected from 852 permanent and temporary broad-band stations in the region to calculate group-velocity dispersion curves. A compilation of >54 000 ray paths provides reliable group-velocity measurements for periods between 2 and 150 s. Path-averaged group velocities calculated at different periods were inverted for 2-D group-velocity maps. To overcome the problem of heterogeneous ray coverage, we used an adaptive grid parametrization for the group-velocity tomographic inversion. We then sample the period-dependent group-velocity field at each cell of a predefined grid to generate 1-D group-velocity dispersion curves, which are subsequently inverted for 1-D Vs models beneath each cell and combined to approximate the 3-D Vs structure of the area. The Vs model shows low velocities at shallow depths (5–10 km) beneath the Mesopotamian foredeep, South Caspian Basin, eastern Mediterranean and the Black Sea, in coincidence with deep sedimentary basins. Shallow high-velocity anomalies are observed in regions such as the Arabian Shield, Anatolian Plateau and Central Iran, which are dominated by widespread magmatic exposures. In the 10–20 km depth range, we find evidence for a band of high velocities (>4.0 km s–1) along the southern Red Sea and Arabian Shield, indicating the presence of upper mantle rocks. Our 3-D velocity model exhibits high velocities in the depth range of 30–50 km beneath western Arabia, eastern Mediterranean, Central Iranian Block, South Caspian Basin and the Black Sea, possibly indicating a relatively thin crust. In contrast, the Zagros mountain range, the Sanandaj-Sirjan metamorphic zone in western central Iran, the easternmost Anatolian plateau and Lesser Caucasus are characterized by low velocities at these depths. Some of these anomalies may be related to thick crustal roots that support the high topography of these regions. In the upper mantle depth range, high-velocity anomalies are obtained beneath the Arabian Platform, southern Zagros, Persian Gulf and the eastern Mediterranean, in contrast to low velocities beneath the Red Sea, Arabian Shield, Afar depression, eastern Turkey and Lut Block in eastern Iran. Our Vs model may be used as a new reference crustal model for the Middle East in a broad range of future studies.