The Phases of QCD in Heavy Ion Collisions and Compact Stars

I review arguments for the existence of a critical point in the QCD phase diagram as a function of temperature and baryon chemical potential. 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.