Two in vitro selection experiments were conducted to determine the RNA sequence requirements for binding ribosomal protein L32 (RPL32) from Saccharomyces cerevisiae. To preserve the wild-type stem-internal loop-stem fold, only a limited portion of the RNA comprising the internal loop region was randomized. Most of the selected RNAs have secondary structures similar to that of the wild-type, and four purines on both sides of the internal loop are highly conserved. Indeed, a pair of 5'-GA-3' dinucleotides is found in all but one of the stem-loop-stem L32 aptamers and these conserved purines may contact the protein directly or form a necessary RNA secondary or tertiary structure. These aptamers have a potential G:U pair bordering the loop adjacent to the conserved GAs, but a cytidine replaces a phylogenetically conserved adenosine at one loop position in many of the selected RNAs. In model RNAs, the cytidine-bearing variant binds protein slightly more strongly than does the wild-type RNA. That the seven-member, 2 + 5 internal loop is important for protein binding is reinforced by the finding that the position, but not the size, of the loop is variable. A minority of the RNA aptamers has three consecutive uridines and may fold into a similar structure, but with the internal loop inverted.