This White Paper summarizes the outcome of the Town Meeting on Phases of QCD that took place January 12-14, 2007 at Rutgers University, as part of the NSAC 2007 Long Range Planning process. The meeting was held in conjunction with the Town Meeting on Hadron Structure, including a full day of joint plenary sessions of the two meetings. Appendix A.1 contains the meeting agenda. This Executive Summary presents the prioritized recommendations that were determined at the meeting. Subsequent chapters present the essential background to the recommendations. While this White Paper is not a scholarly article and contains few references, it is intended to provide the non-expert reader