We report the discovery of the gamma-ray burst GRB 000131 and its optical afterglow. The optical identification was made with the VLT 84 hours after the burst following a BATSE detection and an Inter Planetary Network localization. GRB 000131 was a bright, long-duration GRB, with an apparent precursor signal 62 s prior to trigger. The afterglow was detected in ESO VLT, NTT, and DK1.54m follow-up observations. Broad-band and spectroscopic observations of the spectral energy distribution reveals a sharp break at optical wavelengths which is interpreted as a Ly-alpha absorption edge at 6700 A. This places GRB 000131 at a redshift of 4.500 +/- 0.015. The inferred isotropic energy release in gamma rays alone was approximately 10^54 erg (depending on the assumed cosmology). The rapid power-law decay of the afterglow (index alpha=2.25, similar to bursts with a prior break in the lightcurve), however, indicates collimated outflow, which relaxes the energy requirements by a factor of