A wide range of evolutionary processes have been implicated in the diversification of yuccas and yucca moths, which exhibit ecological relationships that extend from obligate plant-pollinator mutualisms to commensalist herbivory. Prodoxus coloradensis (Lepidoptera: Prodoxidae) is a yucca moth, which feeds on the flowering stalks of three Yucca species as larvae, but does not provide pollination service. To test for evidence of host-associated speciation, we examined the genetic structure of P. coloradensis using mitochondrial (cytochrome oxidase I) and nuclear (elongation factor 1 alpha) DNA sequence data. Multilocus coalescent simulations indicate that moths on different host plant species are characterized by recent divergence and low levels of effective migration, with large effective population sizes and considerable retention of shared ancestral polymorphism. Although geographical distance explains a proportion of the mitochondrial and nuclear DNA variation among moths on different species of Yucca, the effect of host specificity on genetic distance remains significant after accounting for spatial isolation. The results of this study indicate that differentiation within P. coloradensis is consistent with the evolution of incipient species affiliated with different host plants, potentially influenced by sex-biased dispersal and female philopatry.