Abstract Efforts are underway to construct several recoded genomes anticipated to exhibit multi-virus resistance, enhanced non-standard amino acid (NSAA) incorporation, and capability for synthetic biocontainment. Though we succeeded in pioneering the first genomically recoded organism ( Escherichia coli strain C321.ΔA), its fitness is far lower than that of its non-recoded ancestor, particularly in defined media. This fitness deficit severely limits its utility for NSAA-linked applications requiring defined media such as live cell imaging, metabolic engineering, and industrial-scale protein production. Here, we report adaptive evolution of C321.ΔA for more than 1,000 generations in independent replicate populations grown in glucose minimal media. Evolved recoded populations significantly exceed the growth rates of both the ancestral C321.ΔA and non-recoded strains, permitting use of the recoded chassis in several new contexts. We use next-generation sequencing to identify genes mutated in multiple independent populations, and we reconstruct individual alleles in ancestral strains via multiplex automatable genome engineering (MAGE) to quantify their effects on fitness. Several selective mutations occur only in recoded evolved populations, some of which are associated with altering the translation apparatus in response to recoding, whereas others are not apparently associated with recoding, but instead correct for off-target mutations that occurred during initial genome engineering. This report demonstrates that laboratory evolution can be applied after engineering of recoded genomes to streamline fitness recovery compared to application of additional targeted engineering strategies that may introduce further unintended mutations. In doing so, we provide the most comprehensive insight to date into the physiology of the commonly used C321.ΔA strain. Significance Statement After demonstrating construction of an organism with an altered genetic code, we sought to evolve this organism for many generations to improve its fitness and learn what unique changes natural selection would bestow upon it. Although this organism initially had impaired fitness, we observed that adaptive laboratory evolution resulted in several selective mutations that corrected for insufficient translation termination and for unintended mutations that occurred when originally altering the genetic code. This work further bolsters our understanding of the pliability of the genetic code, it will help guide ongoing and future efforts seeking to recode genomes, and it results in a useful strain for non-standard amino acid incorporation in numerous contexts relevant for research and industry.