I review arguments for the existence of a critical pointEin the QCD phase diagram as a function of temperatureTand baryon chemical potential &mgr;. I describe how heavy ion collision experiments at the SPS and RHIC can discover the tell-tale signatures of such a critical point, thus mapping this region of the QCD phase diagram. I then review the phenomena expected in cold dense quark matter: color superconductivity and color-flavor locking. I close with a snapshot of ongoing explorations of the implications of recent developments in our understanding of cold dense quark matter for the physics of compact stars. ©2000 American Institute of Physics.