In 2000, Lamb and Reichart predicted that gamma-ray bursts (GRBs) and their afterglows occur in sufficient numbers and at sufficient brightnesses at very high redshifts (z > 5) to eventually replace quasars as the preferred probe of element formation and reionization in the early universe and to be used to characterize the star-formation history of the early universe, perhaps back to when the first stars formed. Here we report the discovery of the afterglow of GRB 050904 and the identification of GRB 050904 as the first very high redshift GRB. We measure its redshift to be 6.39(+0.11,-0.12), which is consistent with the reported spectroscopic redshift (6.29 +/- 0.01). Furthermore, just redward of Ly-alpha the flux is suppressed by a factor of three on the first night, but returns to expected levels by the fourth night. We propose that this is due to absorption by molecular hydrogen that was excited to rovibrational states by the GRB's prompt emission, but was then overtaken by the jet. Now that very high redshift GRBs have been shown to exist, and at least in this case the afterglow was very bright, observing programs that are designed to capitalize on this science will likely drive a new era of study of the early universe, using GRBs as probes.