Sequence-specific recognition between HIV-1 Rev and viral RNA mediates the nuclear export of the viral mRNA and thus is important for the viral life cycle. HIV Rev binds to its viral RNA target with high affinity and specificity and also binds to an in vitro selected RNA aptamer that has a significantly different sequence from the viral RNA target with a 6-fold higher affinity than its natural target. The high-resolution structures of HIV Rev Arg-rich motif (ARM) in complexes with the wild-type RNA and the RNA aptamer reveal that, despite the significantly different RNA sequences, the two complexes share similar structural features and the protein-RNA interactions are mediated mostly by the Arg side chains in Rev ARM. To gain further insight into the role of these Arg side chains in the sequence-specific protein-RNA recognition, we have characterized the flexibility of these Arg side chains at the interfaces of the two high-affinity complexes using (15)N R(1), R(2), nuclear Overhauser effect, and chemical-shift anisotropy dipolar cross-correlation relaxation measurements. The ARM peptide contains uniformly (13)C/(15)N-labeled Arg residues, and the RNA samples were unlabeled. Despite the apparently similar roles of Arg side chains in both complexes, most of them display a different dynamic behavior in the context of different RNA molecules, and extensive and highly diverse motions have been observed for all of these side chains that interact with RNA. Most of the differences in side-chain dynamics between the complexes cannot be inferred from the three-dimensional structures. Additionally, more than half of the residues have increased flexibility in the Rev-RNA aptamer complex that has a higher affinity. This study provides new insights into ARM-RNA recognition and indicates that retention of conformational flexibility is likely important in high-affinity ARM-RNA recognition.