We derive simple empirical color-redshift relations for z<~4 galaxies in the Hubble Deep Field (HDF) using a linear function of three photometric colors (U-B, B-V, V-I). The dispersion between the estimated redshifts and the spectroscopically observed ones is small for relations derived in several separate color regimes; the dispersions range from {sigma}_z_~=0.03 to 0.1 for z<~2 galaxies, and from {sigma}_z_~=0.14 to 0.25 for z>~2 galaxies. We apply the color-redshift relations to the HDF photometric catalog and obtain estimated redshifts that are consistent with those derived from spectral template fitting methods. The advantage of these color-redshift relations is that they are simple and easy to use and do not depend on the assumption of any particular spectral templates; they provide model independent redshift estimates for z<~4 galaxies using only multiband photometry, and they apply to about 90% of all galaxies. We provide a color-based estimated redshift catalog of HDF galaxies to z<~4. We use the estimated redshifts to investigate the redshift distribution of galaxies in the HDF; we find peaks in the redshift distribution that suggest large-scale clustering of galaxies to at least z~1 and that are consistent with those identified in spectroscopic probes of the HDF.