We report a bacterial system for the evolution of cyclic peptides that makes use of an expanded set of amino acid building blocks. Orthogonal aminoacyl-tRNA synthetase/tRNA(CUA) pairs, together with a split intein system were used to biosynthesize a library of ribosomal peptides containing amino acids with unique structures and reactivities. This peptide library was subsequently used to evolve an inhibitor of HIV protease using a selection based on cellular viability. Two of three cyclic peptides isolated after two rounds of selection contained the keto amino acid p-benzoylphenylalanine (pBzF). The most potent peptide (G12: GIXVSL; X=pBzF) inhibited HIV protease through the formation of a covalent Schiff base adduct of the pBzF residue with the ε-amino group of Lys 14 on the protease. This result suggests that an expanded genetic code can confer an evolutionary advantage in response to selective pressure. Moreover, the combination of natural evolutionary processes with chemically biased building blocks provides another strategy for the generation of biologically active peptides using microbial systems.