Mycoheterotrophic species have abandoned an autotrophic lifestyle and obtain carbon exclusively from mycorrhizal fungi. Although these species have evolved independently in many plant families, such events have occurred most often in the Orchidaceae, resulting in the highest concentration of these species in the tracheophytes. Studies of mycoheterotrophic species' mycobionts have generally revealed extreme levels of mycorrhizal specialization, suggesting that this system is ideal for studying the evolution of mycorrhizal associations. However, these studies have often investigated single or few, often unrelated, species without consideration of their phylogenetic relationships. Herein, we present the first investigation of the mycorrhizal associates of all species of a well-characterized orchid genus comprised exclusively of mycoheterotrophic species. With the employment of molecular phylogenetic methods, we identify the fungal associates of each of nine Hexalectris species from 134 individuals and 42 populations. We report that Hexalectris warnockii associates exclusively with members of the Thelephoraceae, H. brevicaulis and H. grandiflora associate with members of the Russulaceae and Sebacinaceae subgroup A, while each member of the H. spicata species complex associates primarily with unique sets of Sebacinaceae subgroup A clades. These results are consistent with other studies of mycorrhizal specificity within mycoheterotrophic plants in that they suggest strong selection within divergent lineages for unique associations with narrow clades of mycorrhizal fungi. Our results also suggest that mycorrhizal associations are a rapidly evolving characteristic in the H. spicata complex.