Technical Abstract: Seed dispersal by vertebrates is one of the most common and important plant-animal mutualisms, involving an enormous diversity of fruiting plants and frugivorous vertebrates. Even though plant reproduction largely depends on seed dispersal, evolutionary ecologists have been unable to link co-occurring traits in fruits with differences in behavior, perceptive capacity and morphology of fruit-eating vertebrates. Hence, the origin and maintenance of fruit diversity remains largely unexplained. Using a multivariate phylogenetic comparative test with unbiased estimates of odor and color, we demonstrate for the first time that fruit traits evolve in concert and as predicted by differences in the behavior, perceptive capacity and morphology of their frugivorous seed dispersers. Observations at fruiting trees independently confirmed that differences in fig traits predict differences in dispersers. Taken together, these results demonstrate that differences among frugivores have shaped the evolution of fruit traits. More broadly, our results underscore the importance of mutualisms both in generating and in maintaining biodiversity.