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 Cerenkov telescope array and discuss its correlation with the X-ray emission. The gamma-ray emission is measured to be pointlike with an intrinsic source radius less than 4.5'. The differential energy spectrum is fitted well by a power-law function: d Phi/dE = (7.4 +/- 1.3(stat) +/- 1.5(sys))(E/TeV)((-2.31 +/- 0.17stat +/- 0.2sys)) 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-timescale 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.