The genus Rumex includes hermaphroditic, polygamous, gynodioecious, monoecious, and dioecious species, with the dioecious species being represented by different sex-determining mechanisms and sex-chromosome systems. Therefore, this genus represents an exceptional case study to test several hypotheses concerning the evolution of both mating systems and the genetic control of sex determination in plants. Here, we compare nuclear intergenic transcribed spacers and chloroplast intergenic sequences of 31 species of Rumex. Our phylogenetic analysis supports a systematic classification of the genus, which differs from that currently accepted. In contrast to the current view, this new phylogeny suggests a common origin for all Eurasian and American dioecious species of Rumex, with gynodioecy as an intermediate state on the way to dioecy. Our results support the contention that sex determination based on the balance between the number of X chromosomes and the number of autosomes (X/A balance) has evolved secondarily from male-determining Y mechanisms and that multiple sex-chromosome systems, XX/XY1Y2, were derived twice from an XX/XY system. The resulting phylogeny is consistent with a classification of Rumex species according to their basic chromosome number, implying that the evolution of Rumex species might have followed a process of chromosomal reduction from x = 10 toward x = 7 through intermediate stages (x = 9 and x = 8).