We present a three-dimensional, S velocity model of the SE Asian-western Pacific upper mantle with 400-km lateral resolution. Using the novel Automated Multimode Inversion technique, we processed 4038 vertical-component seismograms and extracted 22,708 linear equations with uncorrelated uncertainties that constrain upper mantle structure. We used time-frequency windows to select signal with negligible proportion of scattered energy. The windows included the fundamental Rayleigh mode and S and multiple S waves. The observed range of S velocity variations is the widest (17–18%) in the upper 150 km of the mantle. High-velocity continental roots can reach beyond the present extent of the overlying Archean-Proterozoic crust by 500 km. Beneath some Precambrian units the roots are absent, which can be attributed to deformation and gradual destruction of the ancient lithosphere. At 120–150 km, S velocity beneath some cratons reaches 4.8 km/s; this can be accounted for by thermal and compositional effects. Beneath the Hainan Island area a low-velocity anomaly is observed from near the surface to the bottom of our model; the hot spot-type volcanism here may be caused by the deep-mantle Hainan plume. A low-velocity mantle domain underlies the south central Sea of Japan, surrounded on the surface by intraplate volcanoes. A deep-seismicity gap is present near 40°N in the Pacific slab subducting below and may result from a plume-slab interaction. A high-velocity anomaly is present in the transition zone beneath the northern boundary of the Yangtze Craton. We propose that the anomaly corresponds to subducted continental lithosphere, stagnant atop the 660-km discontinuity.