mRNA molecules are tightly regulated, mostly through interactions with proteins and other RNAs, but the mechanisms that confer the specificity of such interactions are poorly understood. It is clear, however, that this specificity is determined by both the nucleotide sequence and secondary structure of the mRNA. We developed RNApromo, an efficient computational tool for identifying structural elements within mRNAs that are involved in specifying post-transcriptional regulations. Using RNApromo, we predicted putative motifs in sets of mRNAs with substantial experimental evidence for common post-transcriptional regulation, including mRNAs with similar decay rates, mRNAs that are bound by the same RNA binding protein, and mRNAs with a common cellular localization. Our new RNA motif discovery tool reveals unexplored layers of post-transcriptional regulations in groups of RNAs, and is therefore an important step toward a better understanding of the regulatory information conveyed within RNA molecules.