Global replacement of a natural amino acid with an unnatural analogue can result in substantial changes in the physical properties of proteins and generate multiple sites for chemical modification. However, this replacement strategy may cause a loss of protein function, especially as proteins become complex and the number of residues replaced increases. For instance, when 5,5,5-trifluorolecuine (Tfl) was incorporated into a green fluorescent protein (GFP) in place of leucine (Leu), there was about 400-fold reduction of the median fluorescence of the cells expressing the fluorinated protein. To address this problem, we have applied a directed evolution approach involving randomization of the sequence of GFP, expression of GFP mutants under conditions promoting nearly quantitative replacement of Leu with Tfl, and selection of highly-fluorescent mutants by cell sorting. Eleven rounds of error-prone PCR and fluorescence-activated cell sorting yielded a variant of GFP containing 20 amino acid substitutions. The median fluorescence of cells expressing the mutant protein in fluorinated form is improved about 700 fold over the wild-type and is higher than the fluorescence of cells that express “normal” wild-type GFP. The purified fluorinated protein is being characterized with respect to spectral properties, folding, and stability. The success of this approach demonstrates the feasibility of preparing functional proteins of novel composition.