Microbes in fluctuating environments must balance rapid growth against fast adaptation (short lag times). Using proteome allocation models, we show evolution drives populations to an evolutionary stable strategy that optimally balances this trade-off. In predictable environments, populations evolve to "learn" statistical patterns by pre-allocating their proteome according to environmental transition probabilities. This demonstrates how microbes use the proteome as a memory to encode and exploit environmental patterns without neural computation.