Correct decision making is fundamental for all living organisms to thrive under environmental changes. The patterns of environmental variation and the quality of available information define the most favourable strategy among multiple options, from randomly adopting a phenotypic state to sensing and reacting to environmental cues. Cellular memory-the ability to track and condition the time to switch to a different phenotypic state-can help withstand environmental fluctuations. How does memory manifest itself in unicellular organisms? We describe the population-wide consequences of phenotypic memory in microbes through a combination of deterministic modelling and stochastic simulations. Moving beyond binary switching models, our work highlights the need to consider a broader range of switching behaviours when describing microbial adaptive strategies. We show that memory in individual cells generates patterns at the population level coherent with overshoots and non-exponential lag times distributions experimentally observed in phenotypically heterogeneous populations. We emphasise the implications of our work in understanding antibiotic tolerance and, in general, bacterial survival under fluctuating environments.