We relocate nearly 100,000 events that occurred during the period 1964 to 1995 and are well-constrained teleseismically by arrival-time data reported to the International Seismological Centre (ISC) and to the U.S. Geological Survey's National Earthquake Information Center (NEIC). Hypocenter determination is significantly improved by using, in addition to regional and teleseismic P and S phases, the arrival times of PKiKP, PKPdf, and the teleseismic depth phases pP, pwP, and sP in the relocation procedure. A global probability model developed for later-arriving phases is used to independently identify the depth phases. The relocations are compared to hypocenters reported in the ISC and NEIC catalogs and by other sources. Differences in our epicenters with respect to ISC and NEIC estimates are generally small and regionally systematic due to the combined effects of the observing station network and plate geometry regionally, differences in upper mantle travel times between the reference earth models used, and the use of later-arriving phases. Focal depths are improved substantially over most other independent estimates, demonstrating (for example) how regional structures such as downgoing slabs can severely bias depth estimation when only regional and teleseismic P arrivals are used to determine the hypocenter. The new data base, which is complete to about Mw 5.2 and includes all events for which moment-tensor solutions are available, has immediate application to high-resolution definition of Wadati-Benioff Zones (WBZs) worldwide, regional and global tomographic imaging, and other studies of earth structure.