Recorded seismicity for the Yellowstone National Park region, comprising 25,267 earthquakes from November 1972 to December 2002, has been relocated using three-dimensional velocity models and probabilistic earthquake location. In addition, new coda magnitudes for earthquakes between 1984 and 2002 were computed by using an improved coda magnitude equation. Three-dimensional velocity models for earthquake location were computed by inverting subsets of high-quality data of three different periods, 1973–1981, 1984–1994, and 1995–2002, for hypocenter locations and seismic velocities. Earthquakes were relocated by using a nonlinear, probabilistic solution to the earthquake location problem. Fully nonlinear location uncertainties included in the probabilistic solution allow a better and more reliable classification of earthquake locations into four quality classes. Earthquake locations show an improvement in location accuracy with time, which we attribute to improved network geometry and more precise timing of arrival times. No large systematic shifts of the relocated earthquake locations are observed, except a systematic shift of ∼2 km to greater depth. The new relocated earthquake locations show tighter clustering of epicenters and focal depths when compared with original earthquake locations. The most intense seismicity in terms of number of earthquakes and cumulative seismic moment release in the Yellowstone National Park region occurs northwest of the Yellowstone caldera between Hebgen Lake and the northern rim of the caldera. Seismicity within the Yellowstone caldera is diffuse, and shallow individual clusters of earthquakes can be associated with major hydrothermal areas.