Worldwide declines of fish stocks raise concerns about deleterious consequences of harvesting for stock abundances and individual life histories, and call for appropriate recovery strategies. Fishes in exploited stocks mature earlier at either larger or smaller sizes due to both genetic and plastic responses. The latter occur commonly when reduced competition for food leads to faster growth. Using a size-structured consumer–resource model, which accounts for both genetic and plastic responses, we show that fisheries-induced evolutionary changes in individual life history and stock properties can easily become irreversible. As a result of annual spawning, early maturation at small sizes and late maturation at large sizes can become alternative, evolutionarily and ecologically stable states under otherwise identical environmental conditions. Exploitation of late-maturing populations can then induce an evolutionary regime shift to smaller maturation sizes associated with stepwise, 1-year decreases in age at first reproduction. Complete and early fishing moratoria slowly reverse this process, but belated or partial closure of fisheries may accelerate or even instigate further evolution to smaller sizes at maturation. We suggest that stepwise decreases in maturation age can be used as early warnings of upcoming evolutionary changes, and should inspire timely restrictions of fisheries.