The understanding of acceleration mechanisms in active galactic nuclei (AGN) jets and the measurement of the extragalactic-background-light (EBL) density are closely linked and require the detection of a large sample of very-high-energy (VHE) emitting extragalactic objects at varying redshifts. We report here on the discovery with the H.E.S.S. (High Energy Stereoscopic System) atmospheric-Cherenkov telescopes of the VHE Gamma-ray emission from H2356 - 309, an extreme BL Lac object located at a redshift of 0.165. The observations of this object, which was previously proposed as a southern-hemisphere VHE candidate source, were performed between June and December 2004. The total exposure is 38.9 hours live time, after data quality selection, which yields the detection of a signal at the level of 9.0$\sigma$ (standard deviations) .