On induction of cell differentiation, distinct cell phenotypes are encoded by complex genetic networks. These networks can prevent the reversion of established phenotypes even in the presence of significant fluctuations. Here we explore the key parameters that determine the stability of cellular memory by using the yeast galactose-signalling network as a model system. This network contains multiple nested feedback loops. Of the two positive feedback loops, only the loop mediated by the cytoplasmic signal transducer Gal3p is able to generate two stable expression states with a persistent memory of previous galactose consumption states. The parallel loop mediated by the galactose transporter Gal2p only increases the expression difference between the two states. A negative feedback through the inhibitor Gal80p reduces the strength of the core positive feedback. Despite this, a constitutive increase in the Gal80p concentration tunes the system from having destabilized memory to having persistent memory. A model reveals that fluctuations are trapped more efficiently at higher Gal80p concentrations. Indeed, the rate at which single cells randomly switch back and forth between expression states was reduced. These observations provide a quantitative understanding of the stability and reversibility of cellular differentiation states.