Orchids differ from other plants in their extremely small and partly air-filled seeds that can be transported long distances by wind. Seed dispersal in orchids is expected to contribute strongly to overall gene flow, and orchids generally express low levels of genetic differentiation between populations and low pollen to seed flow ratios. However, studies in orchids distributed in northern Europe have often found a poor geographic structuring of genetic variation. Here, we studied geographic differentiation in the marsh orchid Dactylorhiza umbrosa, which is widely distributed in upland regions from Asia Minor to Central Asia. These areas were less affected by Pleistocene ice ages than northern Europe and the orchid should have been able to survive the last ice age in local refugia. In the plastid genome, which is dispersed by seeds, populations at close distance were clearly divergent, but the differentiation still increased with geographic distance, and a significant phylogeographic structure had developed. In the nuclear genome, which is dispersed by both seeds and pollen, populations showed an even stronger correlation between genetic and geographic distance, but average levels of differentiation were lower than in the plastid genome, and no phylogeographic structure was evident. Combining plastid and nuclear data, we found that the ratio of pollen to seed dispersal (mp/ms) decreases with physical distance. Comparison with orchids that grow in parts of Europe that were glaciated during the last ice suggests that a balanced structure of genetic diversity develops only slowly in many terrestrial orchids, despite efficient seed dispersal.