Fleshy-fruited plant species depend on frugivores for seed-dispersal – a widespread mutualism in tropical rainforests. The availability and ecology of frugivores therefore affects the evolution of fruit traits – e.g. large fruits may only be eaten and dispersed by large-bodied frugivores. However, little is known about how interaction-relevant fruit traits, such as fruit size, have influenced diversification rates on macro-evolutionary time-scales. Here, we address this question in the globally-distributed palm family (Arecaceae, >2600 species), using an all-evidence phylogeny (~95% of all palm species), fruit size data (~80% of the species) and Bayesian statistics to infer diversification dynamics. Our results suggest that large-fruited palm lineages (fruits > 4 cm, presumably dispersed by frugivorous megafauna) have lower speciation rates than lineages with small fruits, possibly due to increased gene-flow among palm populations and/or longer generation times. Furthermore, we detect a distinct increase in the extinction rate of large-fruited lineages from 0.5-2.6 Mya till the present, as well as a increase in transition rates from large to small fruits during this time period (compared to palm diversification prior to 2.6 Mya). These results suggest that the extinction of megafauna in the Quaternary may have left its signature on the diversification of palm lineages worldwide.