Local extinctions have cascading effects on ecosystem functions, yet little is known about the potential for the rapid evolutionary change of species in human-modified scenarios. We show that the functional extinction of large-gape seed dispersers in the Brazilian Atlantic forest is associated with the consistent reduction of seed size of a keystone palm species. Among 22 palm populations, areas deprived of large avian frugivores for several decades present smaller seeds than non-defaunated forests, with negative consequences for palm regeneration. Coalescence and phenotypic selection models indicate that seed size reduction most likely occurred within the last 100 years, associated with human-driven fragmentation. The fast-paced defaunation of large vertebrates is most likely causing unprecedented changes in the evolutionary trajectories and community composition of tropical forests.