MicroRNAs (miRNAs) are crucial post-transcriptional regulators that have been extensively studied in Bilateria, a group comprising the majority of extant animals, where more than 30 conserved miRNA families have been identified. By contrast, bilaterian miRNA targets are largely not conserved. Cnidaria is the sister group to Bilateria and thus provides a unique opportunity for comparative studies. Strikingly, like their plant counterparts, cnidarian miRNAs have been shown to predominantly have highly complementary targets leading to transcript cleavage by Argonaute proteins. Here, we assess the conservation of miRNAs and their targets by small RNA sequencing followed by miRNA target prediction in eight species of Anthozoa (sea anemones and corals), the earliest-branching cnidarian class. We uncover dozens of novel miRNAs but only a few conserved ones. Further, given their high complementarity, we were able to computationally identify miRNA targets in each species. Besides evidence for conservation of specific miRNA target sites, which are maintained between sea anemones and stony corals across 500 Myr of evolution, we also find indications for convergent evolution of target regulation by different miRNAs. Our data indicate that cnidarians have only few conserved miRNAs and corresponding targets, despite their high complementarity, suggesting a high evolutionary turnover.