Bacterial communities need different strategies to survive in unpredictable environments. Sensing the chemistry of their surroundings and regulating their metabolic machinery accordingly in order to increase the likelihood of proliferation is an important part of the microbial lifestyle. But this strategy is not optimal if the energetic cost of expressing the sensing apparatus is high relative to the benefit of having it. An alternative survival strategy is also used, therefore, one known as bet-hedging. This occurs when a genetically identical population composed of multiple sub-populations, each expressing a different phenotype, is needed to survive. Although many benefits of non-genetic individuality and variable phenotypes between cells have been elucidated in recent years, the underlying gene regulatory mechanisms that support bet-hedging are less clear. Indeed, is phenotypic bistability a noise-driven process? Or can the cell dynamically, indeed almost deterministically, but subject to stochastic forcing, regulate and adapt some aspects of the bet-hedging phenotype dynamically through time without investing in the costly sensing machinery? We answer this question by showing, using mathematical models and computational simulations, that some gene regulatory networks possess complex, multi-stable dynamics which place each cell in different states at different times in a manner that is evolutionarily optimal for the population. Our predicted single-cell gene expression profiles compare favourably with temporally varying gene expression patterns of a virulence factor of the human pathogen Salmonella enterica serovar Typhimurium that we observe experimentally in the Mother Machine microfluidic device.