The QCD phase diagram appears to be the most important single figure of our field. While recent progress in Lattice QCD (LQCD) and model calculations is impressive, the location of phase boundaries and the exact position of the hypothetical critical point (CP) remains unknown. The available theoretical estimates, however, indicate that the critical point might be in the region of the phase diagram probed by current heavy ion experiments. The Beam Energy Scan (BES) program at RHIC, described in this paper, was launched to expand the experimental study where theory cannot yet reach. Both large RHIC experiments, STAR and PHENIX, are in the process of preparing for the first run. Particularly STAR with its large, uniform acceptance and excellent particle identification capabilities, is uniquely positioned to cover this physics in unprecedented depth and detail.