According to a widely accepted paradigm of microbiology, steady-state growth rates are determined solely by current growth conditions1-3 and adaptations between growth states are rapid, as recently recapitulated by simple resource allocation models4. However, even in microbes overlapping regulatory networks can yield multi-stability or long-term cellular memory. Species like Listeria monocytogenes5 and Bacillus subtilis "distinguish" distinct histories for the commitment to sporulation6, but it is unclear if these states can persist over many generations. Remarkably, studying carbon co-utilization of Escherichia coli, we found that growth rates on combinations of carbon sources can depend critically on the previous growth condition. Growing in identical conditions, we observed differences in growth rates of up to 25% and we did not observe convergence of growth rates over 15 generations. We observed this phenomenon occurs across combinations of different phosphotransferase (PTS) substrates with various gluconeogenic carbon sources and found it to depend on the transcription factor Mlc.