We report the discovery of faint very high energy (VHE, E>100 GeV) gamma-ray emission from the radio galaxy Centaurus A in observations performed with the H.E.S.S. experiment, an imaging atmospheric Cherenkov telescope array consisting of four telescopes located in Namibia. Centaurus A has been observed for more than 120 h. A signal with a statistical significance of 5.0 sigma is detected from the region including the radio core and the inner kpc jets. The integral flux above an energy threshold of ~250 GeV is measured to be ~0.8 % of the flux of the Crab Nebula (apparent luminosity: L(>250 GeV)~2.6x10^39 erg s^-1, adopting a distance of 3.8 Mpc. The spectrum can be described by a power law with a photon index of 2.7 +/- 0.5_stat +/- 0.2_sys. No significant flux variability is detected in the data set. However, the low flux only allows detection of variability on the timescale of days to flux increments above a factor of ~15-20 (3 sigma and 4 sigma, respectively). The discovery of VHE gamma-ray emission from Centaurus A reveals particle acceleration in the source to >TeV energies and, together with M 87, establishes radio galaxies as a class of VHE emitters. ; Comment: 5 pages, 4 figures, accepted for publication in ApJ Letters