The genus Yucca is widely recognized for its pollination mutualism with yucca moths. Analysis of diversification in this interaction has been hampered by the lack of a robust phylogeny for the genus. Here we attempt the first extensive nuclear DNA based assessment of the phylogenetic relationships of Yucca. We used AFLP markers to recover the phylogeny of 87 samples representing 38 Yucca taxa. An analysis based on 4322 markers strongly supported a topology consistent with morphological classification at the section level (capsular-fruited Chaenocarpa, fleshy-fruited Sarcocarpa, and spongy-fruited Clistocarpa). Within Sarcocarpa, all but two of the traditional species were monophyletic. Within Chaenocarpa, the morphologically distinct series Rupicolae was strongly supported. In the remaining Chaenocarpa, a western group (Colorado Plateau southward) and an eastern group (Great Plains, central Texas east to Florida) were recovered. Within these groups, where taxonomic circumscriptions are narrow and historically contested, there was at most limited monophyly of traditional taxa, suggesting rapid recent diversification, introgression, or non-monophyletically circumscribed taxa.