12095 P-wave phase data were selected in this study from four NW-oriented and four NE-oriented explosion sounding survey lines conducted along the coast and midland of Southeast China during the years 2010 and 2012. The 1-D crust P-wave velocity model was obtained in the continental margin of Southeast China (Fujian Province) using the travel time residual as the threshold and performing linear iterative inversion. This crust model includes 5 layers with the velocities being 5.04, 5.44, 6.06, 6.16, 6.39 km s-1, respectively, with the bottom depths being 0.23, 2.82, 6.44, 18.81, 30.42 km, respectively, and the uppermost mantle velocity being 8.08 km s-1. Compared with previous work the four P-wave phase data could effectively reflect the shallow and deep crust characteristics. The joint inversion method involves both the velocity and depth. The results in this paper could therefore be more reasonable and applicable than previous findings, with fairly good control in both the shallow and deep crusts. These findings have practical significance for compiling the earthquake travel time table and precisely locating earthquakes in this area. This work also provides an accurate preliminary model for subsequent 2-D and 3-D velocity structure inversions in the Southeast China (Fujian Province) continental margin.