Most megaherbivores in the Americas went extinct around 10,000 years ago, presumably disrupting the long-distance seed dispersal of large, fleshy-fruited plant species. The neotropical anachronism hypothesis, proposed by Janzen and Martin, suggests that large fruits evolved in response to past selective pressures from now-extinct megafauna. While this explains many key adaptations of ‘megafaunal fruit’ plants, it lacks robust palaeoecological evidence. Here we use a multiproxy approach that provides evidence of frugivory by the extinct South American proboscidean Notiomastodon platensis. Using a machine learning model that reveals the extinction effects of these megafaunal dispersers in modern ecosystems, we show how losing seed dispersal interactions increased the extinction risk of megafaunal fruit plants in regions across South America lacking smaller surrogate dispersers. Our results imply that current ecosystems may undergo further functional changes under continuing anthropogenic pressures.