In this paper we briefly review the evolutionary history of the mutualistic interaction between angiosperms that produce fleshy fruits and their major consumers: frugivorous birds and mammals. Fleshy fruits eaten by these vertebrates are widely distributed throughout angiosperm phylogeny. Similarly, a frugivorous diet has evolved independently many times in birds and mammals. Bird dispersal is more common than mammal-dispersal in all lineages of angiosperms, and we suggest that the evolution of bird fruits may have facilitated the evolution of frugivory in primates. The diets of fruit-eating bats overlap less with those of other kinds of frugivorous vertebrates. With a few exceptions, most families producing vertebrate-dispersed fruit appeared substantially earlier in earth history than families of their vertebrate consumers. It is likely that major radiations of these plants and animals have occurred in the past 30 Ma, in part driven by geological changes and also by the foraging behavior of frugivores in topographically complex landscapes. Overall, this mutualistic interaction has had many evolutionary and ecological consequences for tropical plants and animals for most of the Cenozoic Era. Loss of frugivores and their dispersal services will have a strong negative impact on the ecological and evolutionary dynamics of tropical and subtropical communities.