Yucca moths of the family Prodoxidae demonstrate a remarkable coevolved mutualism with their host plants, species of the genus Yucca. Phylogenetic studies of the evolution of these interactions have been hampered by a lack of a robust phylogeny for this group. We inferred a phylogeny of the Prodoxidae from 780 bp of DNA sequence from the mitochondrial cytochrome oxidase I and II genes and the intervening leucine transfer RNA. Generic relationships derived from mitochondrial DNA variation across 38 prodoxid and two outgroup haplotypes were substantially congruent with earlier morphology-based hypotheses, but molecular data provided enough characters to resolve relationships among many taxa unresolved by morphological characteristics. Similarity of sequence divergence estimates among yucca-feeding lineages suggests that diversification of exploitative strategies in yucca moths occurred during a short period. Our results also highlight the importance of including characters that accumulate changes in both clocklike and episodic fashion in phylogenetic reconstruction.