In this study, we have performed a nonlinear waveform inversion procedure for the basin velocity structure. First, we adopted the Neighborhood algorithm (NA) to search the parameter space and construct velocity model to calculate the travel-time for each station by using the Pseudo bending method. Then we obtained the accepted models which have the minimum travel-time error. Finally, these accepted models are applied to wave simulation which is carried out using a 3D precisely spectral element method (SEM), and via NA to implement the inversion by minimizing the misfit between synthetic and observed seismograms. About the characteristics of above methods, the NA is an efficient tool to search the universe range; the Pseudo Bending method (PB) is very accurate and efficient to calculate the travel time through the 3D velocity structure; as for SEM, it is a high-order numerical method with high accuracy to solve the wave propagation through a complicated structure. These all can be computed efficiently through the parallel computer clusters. We also utilized this procedure to obtain the velocity structure of the Taipei basin. From the final results, we can find that the average travel time error is less than original data, and the consistence between the observed and synthetic waveforms shows that the reliability of the obtained velocity structure. The result makes us not only get better understanding the complex basin structure beneath the Taipei basin area, but can identify waveform characteristics due to velocity heterogeneity and topographic effect. We can clearly identify the shape of the basin from the velocity profiles, and the depth of the basin increased from east to west, where the deepest portion is approximated to 680m which nearby the west edge of the basin. From the above results, we indicate that this procedure not only can efficiently obtain the complex velocity structure of the Taipei basin, but also can obtain the more clear S-wave velocity structure than the result of the seismic reflections within the basin. Otherwise, the obtained velocity structure also can be an initial model to invert the more detailed structures.