The Strait of Gibraltar is the most important barrier disconnecting the landmasses of Europe and Africa on the western Mediterranean extreme. Carex helodes is a wind-pollinated species endemic to the western Mediterranean. Because molecular and cytogenetic data allow the inference of its evolutionary history, we analyzed variations in chromosome number, including meiotic chromosome behavior, amplified fragment length polymorphism (AFLP) fingerprints, and nucleotide substitutions in plastid and nuclear DNA sequences. Cytogeographic results showed that the African populations have stabilized at a single chromosome number of 2n = 74, whereas the most frequent cytotype in Iberia is 2n = 72. Phylogenetic reconstructions of 17 sequences from nine closely related species revealed that C. helodes is monophyletic and that the Moroccan populations are embedded in the Iberian lineages. The haplotype network is also consistent with a European origin of the northern African haplotype. AFLP analysis also revealed hierarchical levels of genetic variation compatible with a founder effect process responsible for the African populations. All sources of evidence support the hypothesis that the Strait of Gibraltar has been an effective gene-flow barrier, generating two isolated evolutionary lineages after their dispersal. Recent connections between the two lineages appear unlikely, whereas active gene flow occurs among populations within the two lineages.