We report the first femtosecond time-resolved measurements of melting dynamics of graphite. A high-reflectivity phase, lasting less than 10 ps, appears when and only when the surface is photoexcited above a critical fluence of 0.13 J/${\mathrm{cm}}^{2}$ needed to produce surface damage. The wavelength, polarization, and fluence dependence of time-resolved reflectivity suggest formation of an initial monovalent metallic phase, which transforms within 30 ps to a low-reflectivity phase, similar to that observed in picosecond reflectivity experiments.