Bacteria prudently regulate their metabolic phenotypes by sensing the availability of specific nutrients, expressing the required genes for their metabolism, and repressing them after specific metabolites are depleted. It is unclear, however, how genetic networks maintain and transmit phenotypic states between generations under rapidly fluctuating environments. By subjecting bacteria to fluctuating carbon sources (glucose and lactose) using microfluidics, we discover two types of non-genetic memory in Escherichia coli and analyze their benefits. First, phenotypic memory conferred by transmission of stable intracellular lac proteins dramatically reduces lag phases under cyclical fluctuations with intermediate timescales (1–10 generations). Second, response memory, a hysteretic behavior in which gene expression persists after removal of its external inducer, enhances adaptation when environments fluctuate over short timescales (<1 generation). Using a mathematical model we analyze the benefits of memory across environmental fluctuation timescales. We show that memory mechanisms provide an important class of survival strategies in biology that improve long-term fitness under fluctuating environments. These results can be used to understand how organisms adapt to fluctuating levels of nutrients, antibiotics, and other environmental stresses.