The serendipitous discovery of an unidentified extended TeV $γ$-ray source close to the galactic plane named HESS J1303-631 at a significance of 21 standard deviations is reported. The observations were performed between February and June 2004 with the HESS stereoscopic system of Cherenkov telescopes in Namibia. HESS J1303-631 was discovered roughly 0.6° north of the binary system PSR B1259-63/SS 2883, the target object of the initial observation campaign which was also detected at TeV energies in the same field of view. HESS J1303-631 is extended with a width of an assumed intrinsic Gaussian emission profile of $σ$ = (0.16 $±$ 0.02)° and the integral flux above 380 GeV is compatible with constant emission over the entire observational period of (17 $±$ 3)% of the Crab Nebula flux. The measured energy spectrum can be described by a power-law dN/dE ˜ E-$Γ$ with a photon index of $Γ$ = 2.44 $±$ 0.05stat $±$ 0.2syst. Up to now, no counterpart at other wavelengths is identified. Various possible TeV production scenarios are discussed.