Because of their extremely low nucleotide mutation rates, plant mitochondrial genes are generally not expected to show variation within species. Remarkably, we found nine distinct cytochrome b sequence haplotypes in the gynodioecious alpine plant Silene acaulis, with two or more haplotypes coexisting locally in each of three sampled regions. Moreover, there is evidence for intragenic recombination in the history of the haplotype sample, implying at least transient heteroplasmy of mitochondrial DNA (mtDNA). Heteroplasmy might be achieved by one of two potential mechanisms, either continuous coexistence of subgenomic fragments in low stoichiometry, or occasional paternal leakage of mtDNA. On the basis of levels of synonymous nucleotide substitutions, the average divergence time between haplotypes is estimated to be at least 15 million years. Ancient coalescence of extant haplotypes is further indicated by the paucity of fixed differences in haplotypes obtained from related species, a pattern expected under trans-specific evolution. Our data are consistent with models of frequency-dependent selection on linked cytoplasmic male-sterility factors, the putative molecular basis of females in gynodioecious populations. However, associations between marker loci and the inferred male-sterility genes can be maintained only with very low rates of recombination. Heteroplasmy and recombination between divergent haplotypes imply unexplored consequences for the evolutionary dynamics of gynodioecy, a widespread plant breeding system.