In this study we attempted to estimate 3-D P-wave velocity structure of northeast India region using the first arrival data of local earthquakes that were recorded by about 77 temporary/permanent local seismic stations. The data set, the published bulletins, include 3494 P-wave travel times and 3064 S–P travel times from 980 local earthquakes that were located with a minimum of six observations. The located earthquakes having a travel-time root mean square (RMS) residual ⩽0.49s and azimuthal gap ⩽180° are selected to compute a 1-D velocity model for the region, which is used as initial model for the subsequent 3-D inversions. Our results demonstrate that the computed 3-D velocity model has significantly improved hypocenter locations of the selected 980 earthquakes by reducing the RMS error (⩽0.06) by about 88% with respect to that by the 1-D velocity model. The reconstructed P-wave velocity (V p ) structure, with relocated events, reveal strong heterogeneity in lateral as well as in vertical direction corresponding to the local and regional geology/tectonics of the region. High V p is mapped beneath the Shillong Plateau–Mikir hills and in the vicinity of Indo-Burma ranges at shallower crust (<10km) suggesting dense crystalline rocks under compressional stress. A prominent NW–SE trending low V p structure is imaged between the Shillong Plateau and Mikir hills at 20km depth, which corresponds to the Kopili fault. The Kopili fault system extends down to 30km depth as evidenced by the low V p . A high V p is imaged below the Mikir hills at 40km depth, which is possibly the stress concentrator for high seismic activity along the Kopili fault, particularly at the fault end. The Bengal basin, south of the Shillong Plateau, is identified as a low V p zone extending down to a depth of about 20km, that indicates the thick alluvium sediments.