The rate at which mutations are generated is central to the pace of evolution. Although this rate is remarkably similar amongst all cellular organisms, bacterial strains with mutation rates 100 fold greater than the modal rates of their species are commonly isolated from natural sources and emerge in experimental populations. Theoretical studies postulate and empirical studies teort the hypotheses that these “mutator” strains evolved in response to selection for elevated rates of generation of inherited variation that enable bacteria to adapt to novel and/or rapidly changing environments. Less clear are the conditions under which selection will favor reductions in mutation rates. Declines in rates of mutation for established populations of mutator bacteria are not anticipated if such changes are attributed to the costs of augmented rates of generation of deleterious mutations. Here we report experimental evidence of evolution towards reduced mutation rates in a clinical isolate of Escherichia coli with an hyper-mutable phenotype due a deletion in a mismatch repair gene, (ΔmutS). The emergence in a ΔmutS background of variants with mutation rates approaching those of the normal rates of strains carrying wild-type MutS was associated with increase in fitness with respect to ancestral strain. We postulate that such an increase in fitness could be attributed to the emergence of mechanisms driving a permanent “aerobic style of life”, the negative consequence of this behavior being regulated by the evolution of mechanisms protecting the cell against increased endogenous oxidative radicals involved in DNA damage, and thus reducing mutation rate. Gene expression assays and full sequencing of evolved mutator and normo-mutable variants supports the hypothesis. In conclusion, we postulate that the observed reductions in mutation rate are coincidental to, rather than, the selective force responsible for this evolution.