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 haloes at early epochs. However, it remains unknown how soon after the Big Bang massive starburst progenitors exist. The measured redshift (z) distribution of dusty, massive starbursts has long been suspected to be biased low in z owing to selection effects, as confirmed by recent findings of systems with redshifts as high as ~5 (refs 2-4). Here we report the identification of a massive starburst galaxy at z = 6.34 through a submillimetre colour-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 per cent 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 in 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.