We have used seismic signals recorded at regional and teleseismic distances to determine precise locations of 19 underground nuclear explosions (13 in vertical shafts, and 6 in horizontal tunnels) carried out between October 1976 and July 1996 at the Lop Nor test site in the southern Xinjiang province of China. In addition to first- and later-arriving phase-pick data from the International Seismological Centre and Chinese bulletins, we use waveform cross-correlation methods to measure relative arrival times between the explosions with an accuracy of about 10 msec. We adapted the double-difference algorithm to work with regional and global network data, and applied it to the combined Lop Nor data set to remove the effects of uncertainty in the Earth model. Specifically, we determined locations of more recent tests to the accuracy of the cross-correlation data while simultaneously determining the relative locations of the older tests, for which digital waveforms are not available, to the accuracy of the phase-pick data. In general, our locations are consistent, at the 90% confidence level, with previously published locations (when compared in a common reference frame), with anthropogenic features from satellite imagery, and with high-resolution elevation data. For four explosions, however, our results indicate that a particular explosion may have been carried out in a different shaft than previously noted, or previously associated features must be ruled out because of their location outside a particular error ellipse. Mislocations of explosions from associated satellite features are less than 1 km for all 13 shaft events. The pattern of tunnel-explosion locations falls within a region of suitable overburden required for containment. Eighteen Lop Nor locations have solution qualities at the GT2 level or better, and are well suited to calibrate IMS stations for the purpose of monitoring compliance with the Comprehensive Nuclear-Test-Ban Treaty.