We report the detection of high excitation CO emission from the most distant quasar currently known, SDSS J114816.64+525150.3 (hereafter J1148+5251), at a redshift z=6.419. The CO (J=6-5) and (J=7-6) lines were detected using the IRAM Plateau de Bure interferometer, showing a width of ~280 km/s. An upper flux limit for the CO (J=1-0) line was obtained from observations with the Effelsberg 100-meter telescope. Assuming no gravitational magnification, we estimate a molecular gas mass of ~2x10^10 M_sun. Using the CO (3-2) observations by Walter et al. (2003), a comparison of the line flux ratios with predictions from a large velocity gradient model suggests that the gas is likely of high excitation, at densities ~10^5 cm^-3 and a temperature ~100 K. Since in this case the CO lines appear to have moderate optical depths, the gas must be extended over a few kpc. The gas mass detected in J1148+5251 can fuel star formation at the rate implied by the far-infrared luminosity for less than 10 million years, a time comparable to the dynamical time of the region. The gas must therefore be replenished quickly, and metal and dust enrichment must occur fast. The strong dust emission and massive, dense gas reservoir at z~6.4 provide further evidence that vigorous star formation is co-eval with the rapid growth of massive black holes at these early epochs of the Universe.