The quasar PKS 1510-089 (z=0.361) was observed with the H.E.S.S. array of imaging atmospheric Cherenkov telescopes during high states in the optical and GeV bands, to search for very high energy (VHE, defined as E >= 0.1 TeV) emission. VHE gamma-rays were detected with a statistical significance of 9.2 standard deviations in 15.8 hours of H.E.S.S. data taken during March and April 2009. A VHE integral flux of I(0.15 TeV < E < 1.0 TeV) = (1.0 +- 0.2 (stat) +- 0.2 (sys) x 10^{-11} cm^{-2}s^{-1} is measured. The best-fit power law to the VHE data has a photon index of Gamma=5.4 +- 0.7 (stat) +- 0.3 (sys). The GeV and optical light curves show pronounced variability during the period of H.E.S.S. observations. However, there is insufficient evidence to claim statistically significant variability in the VHE data. Because of its relatively high redshift, the VHE flux from PKS 1510-089 should suffer considerable attenuation in the intergalactic space due to the extragalactic background light (EBL). Hence, the measured gamma-ray spectrum is used to derive upper limits on the opacity due to EBL, which are found to be comparable with the previously derived limits from relatively-nearby BL Lac objects. Unlike typical VHE-detected blazars where the broadband spectrum is dominated by non-thermal radiation at all wavelengths, the quasar PKS 1510-089 has a bright thermal component in the optical to UV frequency band. Among all VHE detected blazars, PKS 1510-089 has the most luminous broad line region (BLR). The detection of VHE emission from this quasar indicates a low level of gamma-gamma absorption on the internal optical to UV photon field.