The three-dimensional S-wave velocity structure was constructed from Rayleigh wave phase velocities, measured using teleseismic TriNet data. The S-wave velocity maps show some features that are much more distinct than previous tomographic results in Southern California. There is a clear seismic velocity contrast across the San Andreas fault. The North American plate side is systematically slower than the Pacific plate side. Under the Eastern California Shear Zone, there are distinct slow velocity anomalies in the crust, suggesting a close connection to lower viscosity crust, previously concluded from observation of the post-seismic deformation after the Landers earthquake. Major upper mantle features include a fast velocity root under the Transverse Ranges, which is the dominant feature in the upper mantle, and a slow velocity anomaly under the Salton Trough. Our results support that the velocity contrast across the San Andreas fault extends below the Moho.