Cytoplasmic mRNA localization is a mechanism used by many organisms to generate asymmetry and sequester protein activity. In the yeast Saccharomyces cerevisiae, mRNA transport to bud tips of dividing cells is mediated by the binding of She2p, She3p, and Myo4p to coding regions of the RNA. To date, 24 bud-localized mRNAs have been identified, yet the RNA determinants that mediate localization remain poorly understood. Here, we used nonhomologous random recombination to generate libraries of sequences that could be selected for their ability to bind She-complex proteins, thereby providing an unbiased approach for minimizing and mapping localization elements in several transported RNAs. Analysis of the derived sequences and predicted secondary structures revealed short sequence motifs that mediate binding to the She complex and RNA localization to the bud tip in vivo. A predicted single-stranded core CG dinucleotide appears to be an important component of the RNA-protein interface, although other nucleotides contribute in a context-dependent manner. Our findings further our understanding of RNA recognition by the She complex, and the methods used here should be applicable for elucidating minimal RNA motifs involved in many other types of interactions.