Molecular switches have been implicated in the storage of information in biological systems. For small structures such as synapses, these switches are composed of only a few molecules and stochastic fluctuations are therefore of importance. Such fluctuations could potentially lead to spontaneous switch reset that would limit the lifetime of information storage. We have analyzed a model of the calcium/calmodulin-dependent protein kinase II (CaMKII) switch implicated in long-term memory in the nervous system. The bistability of this switch arises from autocatalytic autophosphorylation of CaMKII, a reaction that is countered by a saturable phosphatase-1-mediated dephosphorylation. We sought to understand the factors that control switch stability and to determine the functional relationship between stability and the number of molecules involved. Using Monte Carlo simulations, we found that the lifetime of states of the switch increase exponentially with the number of CaMKII holoenzymes. Switch stability requires a balance between the kinase and phosphatase rates, and the kinase rate must remain high relative to the rate of protein turnover. Thus, a critical limit on switch stability is set by the observed turnover rate (one per 30 h on average). Our computational results show that, depending on the timescale of fluctuations in enzyme numbers, for a switch composed of about 15 CaMKII holoenzymes, the stable persistent activation can span from a few years to a human lifetime.