We report the discovery of very-high-energy (VHE) gamma-ray emission of the binary system PSR B1259-63/SS 2883 of a radio pulsar orbiting a massive, luminous Be star in a highly eccentric orbit. The observations around the 2004 periastron passage of the pulsar were performed with the four 13 m Cherenkov telescopes of the H.E.S.S. experiment, recently installed in Namibia and in full operation since December 2003. Between February and June 2004, a gamma-ray signal from the binary system was detected with a total significance above 13 sigma. The flux was found to vary significantly on timescales of days which makes PSR B1259-63 the first variable galactic source of VHE gamma-rays observed so far. Strong emission signals were observed in pre- and post-periastron phases with a flux minimum around periastron, followed by a gradual flux decrease in the months after. The measured time-averaged energy spectrum above a mean threshold energy of 380 GeV can be fitted by a simple power law F_0(E/1 TeV)^-Gamma with a photon index Gamma = 2.7+-0.2_stat+-0.2_sys and flux normalisation F_0 = (1.3+-0.1_stat+-0.3_sys) 10^-12 TeV^-1 cm^-2 s^-1. This detection of VHE gamma-rays provides unambiguous evidence for particle acceleration to multi-TeV energies in the binary system. In combination with coeval observations of the X-ray synchrotron emission by the RXTE and INTEGRAL instruments, and assuming the VHE gamma-ray emission to be produced by the inverse Compton mechanism, the magnetic field strength can be directly estimated to be of the order of 1 G. ; Comment: 10 pages, 8 figures, accepted in Astronomy and Astrophysics on 2 June 2005, replace: document unchanged, replaced author field in astro-ph entry - authors are all members of the H.E.S.S. collaboration and three additional authors (99+3, see document)