(1) Gynodioecy is a sexual system where females and hermaphrodites co-occur. In most gynodioecious angiosperms, sex is determined by an interaction between mitochondrial male-sterility genes (CMS) that arise via recombination and nuclear restorer alleles that evolve to suppress them. In theory, gynodioecy occurs when multiple CMS types are maintained at equilibrium frequencies by balancing selection. However, some gynodioecious populations contain very high frequencies of females. High female frequencies are not expected under balancing selection, but could be explained by the repeated introduction of novel CMS types. (2) To test for balancing selection and/or the repeated introduction of novel CMS, we characterized cytoplasmic haplotypes from 61 populations of Lobelia siphilitica that vary widely in female frequency. (3) We confirmed that mitotype diversity and female frequency were positively correlated across populations, consistent with balancing selection. However, while low-female populations hosted mostly common mitotypes, high-female populations and female plants hosted mostly rare, recombinant mitotypes likely to carry novel CMS types. (4) Our results suggest that balancing selection maintains established CMS types across this species, but extreme female frequencies result from frequent invasion by novel CMS types. We conclude that balancing selection alone cannot account for extreme population sex-ratio variation within a gynodioecious species.