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