Escherichia coli isolates that were tolerant of incorporation of high proportions of 4-fluorotryptophan were evolved by serial growth. The resultant strain still preferred tryptophan for growth but showed improved growth relative to the parental strain on other tryptophan analogues. Evolved clones fully substituted fluorotryptophan for tryptophan in their proteomes within the limits of mass spectral and amino acid analyses. Of the genes sequenced, many genes were found to be unaltered in the evolved strain; however, three genes encoding enzymes involved in tryptophan uptake and utilization were altered: the aromatic amino acid permease (aroP) and tryptophanyl-tRNA synthetase (trpS) contained several amino acid substitutions, and the tyrosine repressor (tyrR) had a nonsense mutation. While kinetic analysis of the tryptophanyl-tRNA synthetase suggests discrimination against 4-fluorotryptophan, an analysis of the incorporation and growth patterns of the evolved bacteria suggest that other mutations also aid in the adaptation to the tryptophan analogue. These results suggest that the incorporation of unnatural amino acids into organismal proteomes may be possible but that extensive evolution may be required to reoptimize proteins and metabolism to accommodate such analogues.