microRNAs (miRNAs) are a class of small noncoding RNAs that posttranscriptionally regulate a large fraction of genes in animal genomes. We have previously published computational miRNA target predictions in five vertebrates, six flies, and three nematodes. Here, we report a comprehensive study of the "deep" conservation of miRNA targets and conserved 3'UTR (untranslated region) motifs in general across vertebrates, flies, and nematodes. Our data indicate that although many miRNA genes and 3'UTR motifs are well-conserved, miRNA-target relationships have diverged more rapidly, and we explicitly assign each gained or lost miRNA-target relationship to one of the three clades. However, we also identify a small but significant number of deeply conserved miRNA targets and show that these are enriched for essential processes related to development. Finally, we provide lists of 3'UTR motifs that are significantly conserved, and thus likely functional, classified by their distribution in the three clades. We find hundreds of such motifs specific to each clade, dozens specific to each pair of clades, and ten shared by vertebrates, flies, and nematodes. These findings suggest that posttranscriptional control has undergone extensive rewiring during metazoan evolution and that many deeply conserved miRNA-target relationships may be vital subunits of metazoan gene regulatory networks.