Erm methyltransferases are prevalent in pathogenic bacteria and confer resistance to macrolide, lincosamide, and streptogramin B antibiotics by specifically methylating the 23S ribosomal RNA at nucleotide A2058. We have identified motifs within the rRNA substrate that are required for methylation by Erm. Substrate molecules were constructed in a combinatorial manner from two separate sets (top and bottom strands) of short RNA sequences. Modifications, including LNA monomers with locked sugar residues, were incorporated into the substrates to stabilize their structures. In functional substrates, the A2058 methylation target (on the 13- to 19-nucleotide top strand) was displayed in an unpaired sequence immediately following a conserved irregular helix, and these are the specific structural features recognized by Erm. Erm methylation was enhanced by stabilizing the top-strand conformation with an LNA residue at G2056. The bottom strand (nine to 19 nucleotides in length) was required for methylation and was still functional after extensive modification, including substitution with a DNA sequence. Although it remains possible that Erm makes some unspecific contact with the bottom strand, the main role played by the bottom strand appears to be in maintaining the conformation of the top strand. The addition of multiple LNA residues to the top strand impeded methylation; this indicates that the RNA substrate requires a certain amount of flexibility for accommodation into the active site of Erm. The combinatorial approach for identifying small but functional RNA substrates is a step towards making RNA-Erm complexes suitable for cocrystal determination, and for designing molecules that might block the substrate-recognition site of the enzyme.