The binding of the arginine-rich motif (ARM) of HIV Rev protein to its high-affinity site in stem IIB in the Rev response element (RRE) initiates assembly of a ribonucleoprotein complex that mediates the export of essential, incompletely spliced viral transcripts. Many biochemical, genetic, and structural studies of RevRRE IIB have been published, yet the roles of many peptide residues in Rev ARM are unconfirmed by mutagenesis. Rev aptamer I (RAI) is an optimized RRE IIB that binds Rev with higher affinity and for which mutational data are sparse. Randomized-codon libraries of Rev ARM were assayed for their ability to bind RRE IIB and RAI using a bacterial reporter system based on bacteriophage N-nut antitermination. Most Rev ARM residues tolerated substitutions without strong loss of binding to RRE IIB, and all except arginine 39 tolerated substitution without strong loss of binding to RAI. The pattern of critical Rev residues is not the same for RRE IIB and RAI, suggesting important differences between the interactions. The results support and aid the interpretation of existing structural models. Observed clinical variation is consistent with additional constraints on Rev mutation. By chance, we found double mutants of two highly critical residues, arginine 35 (to glycine) and asparagine 40 (to valine or lysine), that bind RRE IIB well, but not RAI. That an apparently distinct binding mode occurs with only two mutations highlights the ability of ARMs to evolve new recognition strategies and supports the application of neutral theories of evolution to proteinRNA recognition. Copyright (c) 2013 John Wiley & Sons, Ltd.