AIMS: The properties of the broad-band emission from the high-frequency peaked BL Lac H 2356-309 (z=0.165) are investigated. METHODS: Very High Energy (VHE; E > 100 GeV) observations of H 2356-309 were performed with the High Energy Stereoscopic System (HESS) from 2004 through 2007. Simultaneous optical/UV and X-ray observations were made with the XMM-Newton satellite on June 12/13 and June 14/15, 2005. NRT radio observations were also contemporaneously performed in 2005. ATOM optical monitoring observations were also made in 2007. RESULTS: A strong VHE signal, ~13 sigma total, was detected by HESS after the four years HESS observations (116.8 hrs live time). The integral flux above 240 GeV is I(>240 GeV) = (3.06 +- 0.26 {stat} +- 0.61 {syst}) x 10^{-12} cm^{-2} s^{-1}, corresponding to ~1.6% of the flux observed from the Crab Nebula. A time-averaged energy spectrum is measured from 200 GeV to 2 TeV and is characterized by a power law (photon index of Gamma = 3.06 +- 0.15 {stat} +- 0.10 {syst}). Significant small-amplitude variations in the VHE flux from H 2356-309 are seen on time scales of months and years, but not on shorter time scales. No evidence for any variations in the VHE spectral slope are found within these data. The XMM-Newton X-ray measurements show a historically low X-ray state, characterized by a hard, broken-power-law spectrum on both nights. CONCLUSIONS: The broad-band spectral energy distribution (SED) of the blazar can be adequately fit using a simple one-zone synchrotron self-Compton (SSC) model. In the SSC scenario, higher VHE fluxes could be expected in the future since the observed X-ray flux is at a historically low level.