The importance of memory in bacterial decision-making is relatively unexplored. We show here that a prior experience of swarming is remembered when Escherichia coli encounters a new surface, improving its future swarming efficiency. We conducted >10,000 single-cell swarm assays to discover that cells store memory in the form of cellular iron levels. This “iron” memory preexists in planktonic cells, but the act of swarming reinforces it. A cell with low iron initiates swarming early and is a better swarmer, while the opposite is true for a cell with high iron. The swarming potential of a mother cell, which tracks with its iron memory, is passed down to its fourth-generation daughter cells. This memory is naturally lost by the seventh generation, but artificially manipulating iron levels allows it to persist much longer. A mathematical model with a time-delay component faithfully recreates the observed dynamic interconversions between different swarming potentials. We demonstrate that cellular iron levels also track with biofilm formation and antibiotic tolerance, suggesting that iron memory may impact other physiologies.