The obligate pollination mutualisms between yucca moths and yuccas are some of the most obvious cases of coevolution, but the phylogenetic origins and extent of coevolution in these interactions are little understood. Ecological and phylogenetic information from the yucca moth family, Prodoxidae, shows that pollination has evolved at least three times from separate moth behaviors. Passive pollination occurs in Greya during nectarine by one species and during oviposition by two other species. Active pollination among prodoxids has evolved only once, in the yucca moths. Several life-history traits necessary for the evolution of obligate mutualism are common traits within the Prodoxidae, and only active pollination and modified mouthparts appear to have been novel traits in the yucca moths. We use moth and host biology in a phylogenetic framework to establish hypotheses for the evolution of active pollination and reciprocal specialization in the form of functional nectarlessness in yuccas.