Gynodioecy is a breeding system where both hermaphroditic and female individuals coexist within plant populations. This dimorphism is the result of a genomic interaction between maternally inherited cytoplasmic male sterility (CMS) genes and bi-parentally inherited nuclear male fertility restorers. As opposed to other gynodioecious species, where every cytoplasm seems to be associated with male sterility, wild beet Beta vulgaris ssp. maritima exhibits a minority of sterilizing cytoplasms among numerous non-sterilizing ones. Many studies on population genetics have explored the molecular diversity of different CMS cytoplasms, but questions remain concerning their evolutionary dynamics. In this paper we report one of the first investigations on phylogenetic relationships between CMS and non-CMS lineages. We investigated the phylogenetic relationships between 35 individuals exhibiting different mitochondrial haplotypes. Relying on the high linkage disequilibrium between chloroplastic and mitochondrial genomes, we chose to analyse the nucleotide sequence diversity of three chloroplastic fragments (trnK intron, trnD–trnT and trnL–trnF intergenic spacers). Nucleotide diversity appeared to be low, suggesting a recent bottleneck during the evolutionary history of B. vulgaris ssp. maritima. Statistical parsimony analyses revealed a star-like genealogy and showed that sterilizing haplotypes all belong to different lineages derived from an ancestral non-sterilizing cytoplasm. These results suggest a rapid evolution of male sterility in this taxon. The emergence of gynodioecy in wild beet is confronted with theoretical expectations, describing either gynodioecy dynamics as the maintenance of CMS factors through balancing selection or as a constant turnover of new CMSs.