M dwarfs are the most numerous stars in our Galaxy with masses between approximately 0.5 and 0.1 solar mass. Many of them show surface activity qualitatively similar to our Sun and generate flares, high X-ray fluxes, and large-scale magnetic fields. Such activity is driven by a dynamo powered by the convective motions in their interiors. Understanding properties of stellar magnetic fields in these stars finds a broad application in astrophysics, including, e.g., theory of stellar dynamos and environment conditions around planets that may be orbiting these stars. Most stars with convective envelopes follow a rotation-activity relationship where various activity indicators saturate in stars with rotation periods shorter than a few days. The activity gradually declines with rotation rate in stars rotating more slowly. It is thought that due to a tight empirical correlation between X-ray and magnetic flux, the stellar magnetic fields will also saturate, to values around ~4kG. Here we report the detection of magnetic fields above the presumed saturation limit in four fully convective M-dwarfs. By combining results from spectroscopic and polarimetric studies we explain our findings in terms of bistable dynamo models: stars with the strongest magnetic fields are those in a dipole dynamo state, while stars in a multipole state cannot generate fields stronger than about four kilogauss. Our study provides observational evidence that dynamo in fully convective M dwarfs generates magnetic fields that can differ not only in the geometry of their large scale component, but also in the total magnetic energy.