The multiwavelength observation of the nearby radio galaxy M87 provides a unique opportunity to study in detail processes occurring in Active Galactic Nuclei from radio waves to TeV gamma-rays. Here we report the detection of gamma-ray emission above 250 GeV from M87 in spring 2007 with the VERITAS atmospheric Cherenkov telescope array and discuss its correlation with the X-ray emission. The gamma-ray emission is measured to be point-like with an intrinsic source radius less than 4.5 arcmin. The differential energy spectrum is fitted well by a power-law function: dPhi/dE=(7.4+-1.3_{stat}+-1.5_{sys})(E/TeV)^{-2.31+-0.17_{stat}+-0.2_{sys}} 10^{-9}m^{-2}s^{-1}TeV^{-1}. We show strong evidence for a year-scale correlation between the gamma-ray flux reported by TeV experiments and the X-ray emission measured by the ASM/RXTE observatory, and discuss the possible short-time-scale variability. These results imply that the gamma-ray emission from M87 is more likely associated with the core of the galaxy than with other bright X-ray features in the jet.