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 the accurate knowledge of the distance to the events. 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 >0.1 GeV. Observations were done with 7-channel imager GROND at the 2.2m MPI/ESO telescope, the SIRIUS instrument at the Nagoya-SAAO 1.4m telescope in South Africa, and the GMOS instrument at Gemini-S. The afterglow photometric redshift of z=4.35+-0.15, based on simultaneous 7-filter observations with the Gamma-Ray Optical and Near-infrared Detector (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 rather surprising. 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 Gamma in GRBs and strengthens the extreme nature of GRB 080916C.