The MAGIC telescopes discovered very high energy (VHE, E>100 GeV) gamma-ray emission coming from the distant Flat Spectrum Radio Quasar (FSRQ) PKS 1222+21 (4C +21.35, z=0.432). It is the second most distant VHE gamma-ray source, with well measured redshift, detected until now. The observation was performed on 2010 June 17 (MJD 55364.9) using the two 17 m diameter imaging Cherenkov telescopes on La Palma (Canary Islands, Spain). The MAGIC detection coincides with high energy MeV/GeV gamma-ray activity measured by the Large Area Telescope (LAT) on board the Fermi satellite. The averaged integral flux above 100 GeV is equivalent to 1 Crab Nebula flux. The VHE flux measured by MAGIC varies significantly within the 30 minutes of exposure implying a flux doubling time of about 10 minutes. The VHE and MeV/GeV spectra, corrected for the absorption by the extragalactic background light, can be described by a single power law with photon index 2.72+/-0.34 between 3 GeV and 400 GeV, consistent with gamma-ray emission belonging to a single component in the jet. The absence of a spectral cutoff at 30-60 GeV (indeed, one finds a strict lower limit Ec>130 GeV) constrains the gamma-ray emission region to lie outside the broad line region, which would otherwise absorb the VHE gamma-rays. Together with the detected fast variability, this challenges present emission models from jets in FSRQs.