We report the discovery of very-high-energy (VHE) g-ray emission of the binary system PSR B 1259-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 HESS experiment, recently installed in Namibia and in full operation since December 2003. Between February and June 2004, a g-ray signal from the binary system was detected with a total significance above 13s. The flux was found to vary significantly on timescales of days which makes PSR B 1259-63 the first variable galactic source of VHE g-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 F0(E/1 TeV)G with a photon index G = 2.7 c 0.2stat c 0.2sys and flux normalisation F0 = (1.3 c 0.1stat c 0.3sys) x 10-12 TeV-1 cm-2 s-1. This detection of VHE g-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 g-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.