Human tRNA(Lys3)UUU is the primer for HIV replication. The HIV-1 nucleocapsid protein, NCp7, facilitates htRNA(Lys3)UUU recruitment from the host cell by binding to and remodeling the tRNA structure. Human tRNA(Lys3)UUU is post-transcriptionally modified, but until recently, the importance of those modifications in tRNA recognition by NCp7 was unknown. Modifications such as the 5-methoxycarbonylmethyl-2-thiouridine at anticodon wobble position-34 and 2-methylthio-N(6)-threonylcarbamoyladenosine, adjacent to the anticodon at position-37, are important to the recognition of htRNA(Lys3)UUU by NCp7. Several short peptides selected from phage display libraries were found to also preferentially recognize these modifications. Evolutionary algorithms (Monte Carlo and self-consistent mean field) and assisted model building with energy refinement were used to optimize the peptide sequence in silico, while fluorescence assays were developed and conducted to verify the in silico results and elucidate a 15-amino acid signature sequence (R-W-Q/N-H-X2-F-Pho-X-G/A-W-R-X2-G, where X can be most amino acids, and Pho is hydrophobic) that recognized the tRNA's fully modified anticodon stem and loop domain, hASL(Lys3)UUU. Peptides of this sequence specifically recognized and bound modified htRNA(Lys3)UUU with an affinity 10-fold higher than that of the starting sequence. Thus, this approach provides an effective means of predicting sequences of RNA binding peptides that have better binding properties. Such peptides can be used in cell and molecular biology as well as biochemistry to explore RNA binding proteins and to inhibit those protein functions.