Accurate seismic event locations derived from regional travel-time arrivals are of critical importance to successful monitoring of small, clandestine nuclear tests. High-quality seismic velocity models have been shown to be an important factor in improving estimates of regional event locations. These facts have motivated our development of new tomographic estimates of upper-mantle velocity for a broad region in southern Asia centered on Pakistan. An initial 3D P-wave velocity model for the region was developed by integrating the results of previous studies related to crustal and upper-mantle velocity structure. We applied a 3D nonlinear tomographic technique to refine the upper-mantle velocity of the model using a large database of regional P-wave arrival times from well-located events. Estimates from checkerboard tests show that spatial resolution is 3° or better over most of our data coverage area. Our results show strong lateral variations in upper-mantle velocities that correlate with major tectonic features and previous geophysical observations. Results from location validation studies, performed by relocating a set of reference events by using only the regional arrivals, indicate that the new 3D model significantly improves regional seismic event location performance.