We present an online catalog of distance determinations for 6036 K giants, most of which are members of the Milky Way's stellar halo. Their medium-resolution spectra from the Sloan Digital Sky Survey/Sloan Extension for Galactic Understanding and Exploration 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 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 from the Galactic center, with 283 stars beyond 50 kpc, forming the largest available spectroscopic sample of distant tracers in the Galactic halo.