Deep sequencing of small RNAs (sRNAs) in developing male strobili of second-generation offspring originating from a nuclear genic male sterile tree of Cryptomeria japonica were performed to characterize sRNA populations in the male strobili at early pollen developmental stages. Comparing to sequences of microRNA (miRNA) families of plant species and sRNAs expressed in the reproductive organs of representative vascular plants, 37 conserved miRNA families were detected, of which eight were ubiquitously expressed in the reproductive organs of land plant species. In contrast, miR1083 was common in male reproductive organs of gymnosperm species but absent in angiosperm species. In addition to conserved miRNAs, 199 novel miRNAs candidates were predicted. The expression patterns of the obtained sRNAs were further investigated to detect the differentially expressed (DE) sRNAs between genic male sterile and fertile individuals. A total of 969 DE sRNAs were obtained and only three known miRNA families were included among them. These results suggest that both conserved and species-specific sRNAs contribute to the development of male strobili in C. japonica.