We report on the detection of very-high energy (VHE, E>100 GeV) gamma-ray emission from NGC 1275, the central radio galaxy of the Perseus cluster of galaxies. The source has been detected by the MAGIC telescopes with a statistical significance of 6.6 sigma above 100 GeV in 46 hr of stereo observations carried out between August 2010 and February 2011. The measured differential energy spectrum between 70 GeV and 500 GeV can be described by a power law with a steep spectral index of Gamma=-4.1+/-0.7stat+/-0.3syst, and the average flux above 100 GeV is F_{gamma}=(1.3+/-0.2stat+/-0.3syst) x 10^-11 cm^-2 s^-1. These results, combined with the power-law spectrum measured in the first two years of observations by the Fermi-LAT above 100 MeV, with a spectral index of Gamma ~ -2.1, strongly suggest the presence of a break or cut-off around tens of GeV in the NGC 1275 spectrum. The light curve of the source above 100 GeV does not show hints of variability on a month time scale. Finally, we report on the nondetection in the present data of the radio galaxy IC 310, previously discovered by the Fermi-LAT and MAGIC. The derived flux upper limit F^{U.L.}_{gamma} (>300 GeV)=1.2 x 10^-12 cm^-2 s^-1 is a factor ~ 3 lower than the mean flux measured by MAGIC between October 2009 and February 2010, thus confirming the year time-scale variability of the source at VHE.