Past global change may have forced animal-dispersed plants with megafaunal fruits to adapt or go extinct, but these processes have remained unexplored at broad spatio-temporal scales. Here, we combine phylogenetic, distributional and fruit size data for more than 2500 palm (Arecaceae) species in a time-slice diversification analysis to quantify how extinction and adaptation have changed over deep time. Our results indicate that extinction rates of palms with megafaunal fruits have increased in the New World since the onset of the Quaternary (2.6 million years ago). In contrast, Old World palms show a Quaternary increase in transition rates towards evolving small fruits from megafaunal fruits. We suggest that Quaternary climate oscillations and concurrent habitat fragmentation and defaunation of megafaunal frugivores in the New World have reduced seed dispersal distances and geographical ranges of palms with megafaunal fruits, resulting in their extinction. The increasing adaptation to smaller fruits in the Old World could reflect selection for seed dispersal by ocean-crossing frugivores (e.g. medium-sized birds and bats) to colonize Indo-Pacific islands against a background of Quaternary sea-level fluctuations. Our macro-evolutionary results suggest that megafaunal fruits are increasingly being lost from tropical ecosystems, either due to extinctions or by adapting to smaller fruit sizes.