Using arrival data of the body waves recorded by seismic stations, we reconstructed the velocity structure of the crust and upper mantle beneath the southeastern edge of the Tibetan Plateau and the northwestern continental margin of the South China Sea through a travel time tomography technique. The result revealed the apparent tectonic variation along the Ailao Shan-Red River fault zone and its adjacent regions. High velocities are observed in the upper and middle crust beneath the Ailao Shan-Red River fault zone and they reflect the character of the fast uplifting and cooling of the metamorphic belt after the ductile shearing of the fault zone, while low velocities in the lower crust and near the Moho imply a relatively active crust-mantle boundary beneath the fault zone. On the west of the fault zone, the large-scale low velocities in the uppermost mantle beneath western Yunnan prove the influence of the mantle heat flow on volcano, hot spring and magma activities, however, the upper mantle on the east of the fault zone shows a relatively stable structure similar to the Yangtze block. The low velocities of the deep mantle beneath the southeastern extending segment of the fault zone are probably related to the mantle convection produced by the pull-apart of the South China Sea.