Background: Sexual system is a key factor affecting the genetic diversity, population structure, genome structure and the evolutionary potential of species. The sexual system androdioecy -- where males and hermaphrodites coexist in populations -- is extremely rare, yet is found in three crustacean groups, barnacles, a genus of clam shrimps Eulimnadia, and in the order Notostraca, the tadpole shrimps. In the ancient crustacean order Notostraca, high morphological conservatism contrasts with a wide diversity of sexual systems, including androdioecy. An understanding of the evolution of sexual systems in this group has been hampered by poor phylogenetic resolution and confounded by the widespread occurrence of cryptic species. Here we use a multigene supermatrix for 30 taxa to produce a comprehensive phylogenetic reconstruction of Notostraca. Based on this phylogenetic reconstruction we use character mapping techniques to investigate the evolution of sexual systems. We also tested the hypothesis that reproductive assurance has driven the evolution of androdioecy in Notostraca. Results: Character mapping analysis showed that sexual system is an extremely flexible trait within Notostraca, with repeated shifts between gonochorism and androdioecy, the latter having evolved a minimum of five times. In agreement with the reproductive assurance hypothesis androdioecious notostracans are found at significantly higher latitudes than gonochoric ones indicating that post glacial re-colonisation may have selected for the higher colonisation ability conferred by androdioecy. Conclusions: In contrast to their conserved morphology, sexual system in Notostraca is highly labile and the rare reproductive mode androdioecy has evolved repeatedly within the order. Furthermore, we conclude that this lability of sexual system has been maintained for at least 250 million years and may have contributed to the long term evolutionary persistence of Notostraca. Our results further our understanding of the evolution of androdioecy and indicate that reproductive assurance is a recurrent theme involved in the evolution of this sexual system.