The evolution of female mating preferences is an important key to understanding the evolution of signal diversity. Several hypotheses for preference evolution invoke different processes but all can produce the same end results: thus comparisons of extant traits and preferences within and among populations have made little progress in discriminating among competing hypotheses. Some of these hypotheses, however, do make different predictions as to the historical sequence of trait-preference evolution, and thus can be discriminated with appropriate phylogenetic analyses. We explore this approach in an analysis of the evolution of calls and call preferences in a monophyletic group of frogs, the Physalaemus pustulosus species group. In this clade there are pre-existing preferences for four call traits. These data reject hypotheses that invoke coevolution (good genes, runaway sexual selection) and females evolving preferences to choose males providing better resources, and instead support the hypothesis of sensory exploitation that suggests that males evolve traits that match pre-existing biases in the female's sensory system. We suggest that some of the difficulty in understanding preference evolution might derive from defining a preference only by those extant stimuli that elicit the preference. Our results suggest that preferences might be more general, and that signal diversity might arise from alternative means for eliciting the same preference. Furthermore, we discuss some difficulties with utilizing both population-based comparisons and phylogenetic approaches and suggest that the greatest progress will be made by addressing the problem of preference evolution at several levels of analysis.