For the first time an excess of photons above an energy threshold of 730 GeV from the giant radio galaxy M87 has been measured at a significance level above 4 sigma. The data have been taken during the years 1998 and 1999 with the HEGRA stereoscopic system of 5 imaging atmospheric Cherenkov telescopes. The excess of 107.4 +- 26.8 events above 730 GeV corresponds to an integral flux of 3.3% of the Crab flux or N_gamma(E > 730 GeV) = (0.96 +- 0.23) * 10^(-12) phot.cm^(-2)s^(-1). M87 is located at the center of the Virgo cluster of galaxies at a relatively small redshift of z = 0.00436 and is a promising candidate among the class of giant radio galaxies for the emission of TeV gamma-radiation. The detection of TeV gamma-rays from M87 -- if confirmed -- would establish a new class of extragalactic source in this energy regime since all other AGN detected to date at TeV energies are BL Lac type objects.