Massive present-day early-type (elliptical and lenticular) galaxies probably gained the bulk of their stellar mass and heavy elements through intense, dust-enshrouded starbursts - that is, increased rates of star formation - in the most massive dark matter halos at early epochs. However, it remains unknown how soon after the Big Bang such massive starburst progenitors exist. The measured redshift distribution of dusty, massive starbursts has long been suspected to be biased low in redshift owing to selection effects, as confirmed by recent findings of systems out to redshift z~5. Here we report the identification of a massive starburst galaxy at redshift 6.34 through a submillimeter color-selection technique. We unambiguously determined the redshift from a suite of molecular and atomic fine structure cooling lines. These measurements reveal a hundred billion solar masses of highly excited, chemically evolved interstellar medium in this galaxy, which constitutes at least 40% of the baryonic mass. A maximum starburst converts the gas into stars at a rate more than 2,000 times that of the Milky Way, a rate among the highest observed at any epoch. Despite the overall downturn of cosmic star formation towards the highest redshifts, it seems that environments mature enough to form the most massive, intense starbursts existed at least as early as 880 million years after the Big Bang.