Hox genes encode a family of transcriptional regulators that operate differential developmental programs along the anteroposterior axis of bilateral animals. Regulatory changes affecting Hox gene expression are believed to have been crucial for the evolution of animal body plans. In Drosophila melanogaster, Hox expression is post-transcriptionally regulated by microRNAs (miRNAs) acting on target sites located in the 3' untranslated regions (3'UTRs) of Hox mRNAs. Notably, recent work has shown that during D. melanogaster development Hox genes produce mRNAs with variable 3'UTRs (short and long forms) in different sets of tissues as a result of alternative polyadenylation; importantly, Hox short and long 3'UTRs contain very different target sites for miRNAs. Here, we use a computational approach to explore the evolution of Hox 3'UTRs treated with especial regard to miRNA regulation. Our work is focused on the 12 Drosophila species for which genomic sequences are available and shows, first, that alternative polyadenylation of Hox transcripts is a feature shared by all drosophilids tested in the study. Second, that the regulatory impact of miRNAs is evolving very fast within the Drosophila group. Third, that in contrast to the low degree of primary sequence conservation, Hox 3'UTR regions within the group show very similar RNA topology indicating that RNA structure is under strong selective pressure. Finally, we also demonstrate that Hox alternative polyadenylation can remodel the control regions seen by miRNAs by at least two mechanisms: via adding new cis-regulatory sequences-in the form of miRNA target sites-to short 3'UTR forms as well as by modifying the regulatory impact of miRNA target sites in short 3'UTR forms through changes in RNA secondary structure caused by the use of distal polyadenylation signals.