Stringent searches for microRNAs (miRNAs) have so far only identified these molecules in animals, land plants, chlorophyte green algae, slime molds and brown algae. The identification of miRNAs in brown algae was based on the analysis of a single species, the filamentous brown alga Ectocarpus sp. Here, we have used deep sequencing of small RNAs and a recently published genome sequence to identify miRNAs in a second brown alga, the kelp Saccharina japonica. S. japonica possesses a large number of miRNAs (117) and these miRNAs are highly diverse, falling into 98 different families. Surprisingly, none of the S. japonica miRNAs share significant sequence similarity with the Ectocarpus sp. miRNAs. However, the miRNA repertoires of the two species share a number of structural and genomic features indicating that they were generated by similar evolutionary processes and therefore probably evolved within the context of a common, ancestral miRNA system. This lack of sequence similarity suggests that miRNAs evolve rapidly in the brown algae (the two species are separated by ~95 Myr of evolution). The sets of predicted targets of miRNAs in the two species were also very different suggesting that the divergence of the miRNAs may have had significant consequences for miRNA function.