Prolonged stationary phase is an approximation of natural environments presenting a range of stresses. Survival in prolonged stationary phase requires alternative metabolic pathways for survival. This study describes the repertoire of mutations accumulating in starving Escherichia coli populations in lysogeny broth. A wide range of mutations accumulates over the course of 1 month in stationary phase. Single nucleotide polymorphisms (SNPs) constitute 64% of all mutations. A majority of these mutations are nonsynonymous and are located at conserved loci. There is an increase in genetic diversity in the evolving populations over time. Computer simulations of evolution in stationary phase suggest that the maximum frequency of mutations observed in our experimental populations cannot be explained by neutral drift. Moreover, there is frequent genetic parallelism across populations, suggesting that these mutations are under positive selection. Finally, functional analysis of mutations suggests that regulatory mutations are frequent targets of selection. IMPORTANCE Prolonged stationary phase in bacteria, contrary to its name, is highly dynamic, with extreme nutrient limitation as a predominant stress. Stationary-phase cultures adapt by rapidly selecting a mutation(s) that confers a growth advantage in stationary phase (GASP). The phenotypic diversity of starving E. coli populations has been studied in detail; however, only a few mutations that accumulate in prolonged stationary phase have been described. This study documented the spectrum of mutations appearing in Escherichia coli during 28 days of prolonged starvation. The genetic diversity of the population increases over time in stationary phase to an extent that cannot be explained by random, neutral drift. This suggests that prolonged stationary phase offers a great model system to study adaptive evolution by natural selection.