The Qilian Orogen Zone (QOZ), located in the north margin of the Tibetan Plateau, is the key area for understanding the deformation and dynamics process of Tibet. Numerous geological and geophysical studies have been carried out on the mechanics of the Tibetan Plateau deformation and uplift; however, the detailed structure and deformation style of the Qilian Orogen Zone have remained uncertain due to poor geophysical data coverage and limited resolution power of inversion algorithms. In this study, we analyze the P-wave velocity structure beneath the Qilian Orogen Zone, obtained by applying multi-scale seismic tomography technique to P-wave arrival time data recorded by regional seismic networks. The seismic tomography algorithm used in this study employs sparsity constraints on the wavelet representation of the velocity model via L1-norm regularization. This algorithm can deal efficiently with uneven-sampled volumes, and can obtain multi-scale images of the velocity model. Our results can be summarized as follows: (1) The crustal velocity structure is strongly inhomogeneous and consistent with the surface geological setting. Significant low-velocity anomalies exist in the crust of northeastern Tibet, and slight high-velocity anomalies exist beneath the Qaidam Basin and Alxa terrane. (2) The Qilian Orogen Zone can be divided into two main parts by the Laji Shan Faults: the northwestern part with a low-velocity feature, and the southeastern part with a high-velocity feature at the upper and middle crust. (3) Our tomographic images suggest that northwestern and southeastern Qilian Orogen Zones have undergone different tectonic processes. In the northwest Qilian Orogen Zone, the deformation and growth of the Northern Tibetan Plateau has extended to the Heli Shan and Beida Shan region by northward over-thrusting at the upper crust and thickening in the lower crust. We speculate that in the southeast Qilian Orogen Zone the deformation and growth of the Northern Tibet Plateau were of strike-slip style at the upper crust; in the lower crust, the evidence suggests ductile shear extrusion style and active frontage extension to the Alxa terrane. (4) The multi-scale seismic tomography technique provides multi-scale analysis and sparse constraints, which has allowed to us obtain stable, high-resolution results.