Although coevolution is acknowledged to occur in nature, coevolutionary patterns in symbioses not involving species-to-species relationships are poorly understood. Mycorrhizal plants are thought to be too generalist to coevolve with their symbiotic fungi; yet some plants, including some orchids, exhibit strikingly narrow mycorrhizal specificity. Here, we assess the evolutionary history of mycorrhizal specificity in the lady's slipper orchid genus, Cypripedium. We sampled 90 populations of 15 taxa across three continents, using DNA methods to identify fungal symbionts and quantify mycorrhizal specificity. We assessed phylogenetic relationships among sampled Cypripedium taxa, onto which we mapped mycorrhizal specificity. Cypripedium taxa associated almost exclusively with fungi within family Tulasnellaceae. Ancestral specificity appears to have been narrow, followed by a broadening after the divergence of C. debile. Specificity then narrowed, resulting in strikingly narrow specificity in most of the taxa in this study, with no taxon rewidening to the same extant as basal members of the genus. Sympatric taxa generally associated with different sets of fungi, and most clades of Cypripedium-mycorrhizal fungi were found throughout much of the northern hemisphere, suggesting that these evolutionary patterns in specificity are not the result of biogeographic lack of opportunity to associate with potential partners. Mycorrhizal specificity in genus Cypripedium appears to be an evolvable trait, and associations with particular fungi are phylogenetically conserved.