We used network-level conservation between pairs of fly (Drosophila melanogaster/D. pseudoobscura) and worm (Caenorhabditis elegans/C. briggsae) genomes to detect highly conserved mRNA motifs in 3' untranslated regions. Many of these elements are complementary to the 5' extremity of known microRNAs (miRNAs), and likely correspond to their target sites. We also identify known targets of RNA-binding proteins, and many novel sites not yet known to be functional. Coherent sets of genes with similar function often bear the same conserved elements, providing new insights into their cellular functions. We also show that target sites for distinct miRNAs are often simultaneously conserved, suggesting combinatorial regulation by multiple miRNAs. A genome-wide search for conserved stem-loops, containing complementary sequences to the novel sites, revealed many new candidate miRNAs that likely target them. We also provide evidence that posttranscriptional networks have undergone extensive rewiring across distant phyla, despite strong conservation of regulatory elements themselves.