Context. The detection of GeV photons from gamma-ray bursts (GRBs) has important consequences for the interpretation and modelling of these most-energetic cosmological explosions. The full exploitation of the high-energy measurements relies, however, on accurate knowledge of the distance to the events. Aims. Here we report on the discovery of the afterglow and subsequent redshift determination of GRB 080916C, the first GRB detected by the Fermi Gamma-Ray Space Telescope with high significance detection of photons at energies >0.1 GeV. Methods. Observations were done with the 7-channel “Gamma-Ray Optical and Near-infrared Detector” (GROND) at the 2.2 m MPI/ESO telescope, the SIRIUS instrument at the Nagoya-SAAO 1.4 m telescope in South Africa, and the GMOS instrument at Gemini-S. Results. The afterglow photometric redshift of $z = 4.35 \pm 0.15$, based on simultaneous 7-filter observations with GROND, places GRB 080916C among the top 5% most distant GRBs and makes it the most energetic GRB known to date. The detection of GeV photons from such a distant event is unexpected because of the predicted opacity due to interaction with the extragalactic background light. The observed gamma-ray variability in the prompt emission, together with the redshift, suggests a lower limit for the Lorentz factor of the ultra-relativistic ejecta of $\Gamma > 1090$. This value rivals any previous measurements of Γ in GRBs and strengthens the extreme nature of GRB 080916C.