Abstract: Laboratory experiments with microorganisms offer unique opportunities to study evolution in action. We used next-generation DNA sequencing data to reconstruct the dynamics of genome evolution from the 40,000-generation frozen "fossil record" of an Escherichia coli population. Surprisingly, the rate at which beneficial mutations substituted in this population was relatively constant at first, despite a dramatically decelerating rate of adaptation. In contrast, the neutral substitution rate and amount of genetic diversity in the population were highly variable over time and increased dramatically after a mutator phenotype evolved. Additional experiments that "replay the tape" of early evolution in this population show that a specific lineage is able to reproducibly overtake competitors of higher fitness because it maintains a greater potential for further adaptation.