In the initial years of operation, experiments at the Relativistic Heavy Ion Collider (RHIC) have identified a new form of matter formed in nucleus–nucleus collisions at energy densities more than 100 times that of a cold atomic nucleus. Measurements and comparison with relativistic hydrodynamic models indicate that the matter thermalizes in an unexpectedly short time, has an energy density at least 15 times larger than needed for color deconfinement, has a temperature about twice the critical temperature predicted by lattice QCD, and appears to exhibit collective motion with ideal hydrodynamic properties–a “perfect liquid” that appears to flow with a near-zero viscosity to entropy ratio–lower than any previously observed fluid and perhaps close to a universal lower bound. However, a fundamental understanding of the medium seen in heavy-ion collisions at RHIC does not yet exist. The most important scientific challenge for the field in the next decade is the quantitative exploration of the new state of nuclear matter. That will require new data that will, in turn, require enhanced capabilities of the RHIC detectors and accelerator. In this report we discuss the scientific opportunities for an upgraded RHIC facility–RHIC II–in conjunction with improved capabilities of the two large RHIC detectors, PHENIX and STAR. We focus solely on heavy flavor probes. Their production rates are calculable using the well-established techniques of perturbative QCD and their sizable interactions with the hot QCD medium provide unique and sensitive measurements of its crucial properties making them one of the key diagnostic tools available to us.