We report on the detection of flaring activity from the Fanaroff-Riley I radio galaxy NGC 1275 in very-high-energy (VHE, E > 100 GeV) gamma rays with the Major Atmospheric Gamma Imaging Cherenkov (MAGIC) telescopes. The observations were performed between 2016 September and 2017 February, as part of a monitoring programme. The brightest outburst, with ˜1.5 times the Crab Nebula flux above 100 GeV (C.U.), was observed during the night between 2016 December 31 and 2017 January 1. The flux is fifty times higher than the mean flux previously measured in two observational campaigns between 2009 October and 2010 February and between 2010 August and 2011 February. Significant variability of the day-by-day light curve was measured. The shortest flux-doubling timescale was found to be of (611 ± 101) min. The spectra calculated for this period are harder and show a significant curvature with respect to the ones obtained in the previous campaigns. The combined spectrum of the MAGIC data during the strongest flare state and simultaneous data from the Fermi-LAT around 2017 January 1 follows a power law with an exponential cutoff at the energy (492 ± 35) GeV. We further present simultaneous optical flux density measurements in the R-band obtained with the Kungliga Vetenskaps Akademien (KVA) telescope and investigate the correlation between the optical and gamma-ray emission. Due to possible internal pair-production, the fast flux variability constrains the Doppler factor to values that are inconsistent with a large viewing angle as observed in the radio band. We investigate different scenarios for the explanation of fast gamma-ray variability, namely emission from magnetospheric gaps, relativistic blobs propagating in the jet (mini-jets), or an external cloud (or star) entering the jet. We find that the only plausible model to account for the luminosities here observed would be the production of gamma rays in a magnetospheric gap around the central black hole, only in the eventuality of an enhancement of the magnetic field threading the hole from its equipartition value with the gas pressure in the accretion flow. The observed gamma-ray flare therefore challenges all the discussed models for fast variability of VHE gamma-ray emission in active galactic nuclei.