Synaptic plasticity is key to the brain’s life-long learning capabilities, but the link between changes at individual synapses and emerging network properties remains elusive. Recent meta-learning approaches have started automating the search through the space of possible plasticity rules for plausible candidates. However, these approaches were either limited to narrow sets of rules, or did not investigate any network function beyond stability. Here, we identify thousands of co-active excitatory(E)-to-E, E-to-inhibitory(I), I-to-E and I-to-I Hebbian rules that elicit learning in large recurrent spiking networks. Strikingly, the vast majority of rules that kept network dynamics stable also elicited memories, with diverse flavours of engram formation, recall and graceful forgetting reminiscent of experimental data. Further analysis revealed that this unexpectedly common byproduct of network stabilization was enabled by hysteresis, i.e., plasticity shapes connectivity to stabilise network dynamics in a way that depends on past inputs. In practice, this dependency created robust and readable memory traces lasting for seconds to hours depending on the rule. We thus set to develop a normative theory of which stabilizing plasticity rules can reliably form memories via hysteresis. We move to an analytically tractable setting ---linear rate networks--- and compare broad classes of plasticity: Hebbian, non-Hebbian and gradient-based. Surprisingly, an “optimal” rule ---in terms of minimising total weight changes--- would not generate hysteresis, potentially explaining why this phenomenon may have gone unnoticed so far. Overall, we show that memorization and forgetting is a widespread property of a vast subset of co-active simple Hebbian rules. These rules can account for various experimental observations of neural circuits during learning. Paradoxically, letting several plasticity rules cooperate in large spiking networks simplified the problem and eased the need for fine-tuning prevalent in the field. We propose a general underlying mechanism: memory as a byproduct of stability through hysteresis.