Animal seed dispersal provides an important ecosystem service by strongly benefiting plant communities. There are several theoretical studies on the ecology of plant-animal seed-disperser interactions, but few studies have explored the evolution of this mutualism. Moreover, these studies ignore plant life-history and frugivore foraging behavior. Thus, it remains an open question what the conditions for the diversification of fruit traits are, in spite of the multitude of empirical studies on fruit trait diversity. Here we study the evolution of fruit traits using a spatially-explicit individual-based model, which considers the costs associated with adaptations inducing dispersal by frugivory, as well as frugivore foraging behavior and abundance. Our model predicts that these costs are the main determinants of the evolution of fruit traits, and that when the costs are not very high, the evolution of larger fruit traits (e.g. fleshy/colorful fruits) is controlled by the choosiness and response thresholds of the frugivores as well as their numerical abundance.