A new tomography method, the adaptive moving window, is introduced and applied to construct the velocity structure of the crust and upper mantle of China and surrounding areas. More than 345,000 high-quality compressional body-wave phase data extracted from the Annual Bulletin of Chinese Earthquakes spanning from 1990 to 1998 are used. The area of interest is represented horizontally by 2338 points with 1° intervals. Each point is assigned a window (a cell or a region centered at each point) whose size is varied depending upon the ray path density. A five-layer 1D model from surface down to uppermost mantle is then determined at each point by performing a Monte Carlo random search where earthquake locations are held constant. Combining and smoothing the obtained 1D models, an equivalent 3D model is achieved. The predicted travel times through the 3D model match very well with the observed ones from local to regional distances. The model has a good correlation with tectonic features and is generally consistent with the existing models constructed by other researchers. Our model gives detailed information about structure and is feasible for application to high-quality earthquake location problems.