A deep observation campaign carried out by the High Energy Stereoscopic System (HESS) on Centaurus A enabled the discovery of gamma-rays from the blazar 1ES 1312-423, 2 degrees away from the radio galaxy. With a differential flux at 1 TeV of phi(1 TeV) = (1.9 +/- 0.6(stat) +/- 0.4(sys)) x 10(-13) cm(-2) s(-1) TeV-1 corresponding to 0.5 per cent of the Crab nebula differential flux and a spectral index Gamma = 2.9 +/- 0.5(stat) +/- 0.2(sys), 1ES 1312-423 is one of the faintest sources ever detected in the very high energy (E > 100 GeV) extragalactic sky. A careful analysis using three and a half years of Fermi Large Area Telescope (Fermi-LAT) data allows the discovery at high energies (E > 100 MeV) of a hard spectrum (Gamma = 1.4 +/- 0.4(stat) +/- 0.2(sys)) source coincident with 1ES 1312-423. Radio, optical, UV and X-ray observations complete the spectral energy distribution of this blazar, now covering 16 decades in energy. The emission is successfully fitted with a synchrotron self-Compton model for the non-thermal component, combined with a blackbody spectrum for the optical emission from the host galaxy.