The current consensus is that galaxies begin as small density fluctuations in the early Universe and grow by in situ star formation and hierarchical merging. Stars begin to form relatively quickly in sub-galactic-sized building blocks called haloes which are subsequently assembled into galaxies. However, exactly when this assembly takes place is a matter of some debate. Here we report that the stellar masses of brightest cluster galaxies, which are the most luminous objects emitting stellar light, some 9 billion years ago are not significantly different from their stellar masses today. Brightest cluster galaxies are almost fully assembled 4-5 billion years after the Big Bang, having grown to more than 90 per cent of their final stellar mass by this time. Our data conflict with the most recent galaxy formation models based on the largest simulations of dark-matter halo development. These models predict protracted formation of brightest cluster galaxies over a Hubble time, with only 22 per cent of the stellar mass assembled at the epoch probed by our sample. Our findings suggest a new picture in which brightest cluster galaxies experience an early period of rapid growth rather than prolonged hierarchical assembly.