  We present an online catalog of distance determinations for $\rm 6036$ K
giants, most of which are members of the Milky Way's stellar halo. Their
medium-resolution spectra from SDSS/SEGUE are used to derive metallicities and
rough gravity estimates, along with radial velocities. Distance moduli are
derived from a comparison of each star's apparent magnitude with the absolute
magnitude of empirically calibrated color-luminosity fiducials, at the observed
$(g-r)_0$ color and spectroscopic [Fe/H]. We employ a probabilistic approach
that makes it straightforward to properly propagate the errors in
metallicities, magnitudes, and colors into distance uncertainties. We also fold
in ${\it prior}$ information about the giant-branch luminosity function and the
different metallicity distributions of the SEGUE K-giant targeting
sub-categories. We show that the metallicity prior plays a small role in the
distance estimates, but that neglecting the luminosity prior could lead to a
systematic distance modulus bias of up to 0.25 mag, compared to the case of
using the luminosity prior. We find a median distance precision of $16\%$, with
distance estimates most precise for the least metal-poor stars near the tip of
the red-giant branch. The precision and accuracy of our distance estimates are
validated with observations of globular and open clusters. The stars in our
catalog are up to 125 kpc distant from the Galactic center, with 283 stars
beyond 50 kpc, forming the largest available spectroscopic sample of distant
tracers in the Galactic halo.

Astrophysics of Galaxies