We report on the identification of the highest redshift submm-selected source currently known: LESSJ033229.4-275619. This source was detected in the Large Apex BOlometer CAmera (LABOCA) Extended Chandra Deep Field South (ECDFS) Submillimetre Survey (LESS), a sensitive 870-um survey (~1.2-mJy rms) of the full 30'x30' ECDFS with the LABOCA camera on the Atacama Pathfinder EXperiment (APEX) telescope. The submm emission is identified with a radio counterpart for which optical spectroscopy provides a redshift of z=4.76. We show that the bolometric emission is dominated by a starburst with a star formation rate of ~1000 Msun/yr, although we also identify a moderate luminosity Active Galactic Nucleus (AGN) in this galaxy. Thus it has characteristics similar to those of z~2 submm galaxies (SMGs), with a mix of starburst and obscured AGN signatures. This demonstrates that ultraluminous starburst activity is not just restricted to the hosts of the most luminous (and hence rare) QSOs at z~5, but was also occurring in less extreme galaxies at a time when the Universe was less than 10% of its current age. Assuming that we are seeing the major phase of star formation in this galaxy, then we demonstrate that it would be identified as a luminous distant red galaxy at z~3 and that the current estimate of the space density of z>4 SMGs is only sufficient to produce ~10% of the luminous red galaxy population at these early times. However, this leaves open the possibility that some of these galaxies formed through less intense, but more extended star formation events. If the progenitors of all of the luminous red galaxies at z~3 go through an ultraluminous starburst at z>4 then the required volume density of z>4 SMGs will exceed that predicted by current galaxy formation models by more than an order of magnitude.