Natural protected areas are critically important in the effort to prevent large-scale megafaunal extinctions caused by hunting and habitat degradation. Yet such protection can lead to rapid increases in megafauna populations. Understanding ecosystem-scale responses of vegetation to changing megafaunal populations, such as the case of the African elephant Loxodonta africana in savannas, requires large-scale, high-resolution monitoring over time. From 2008 to 2014, we repeatedly surveyed the fate of more than 10.4 million woody plant canopies throughout the Kruger National Park, South Africa using airborne Light Detection and Ranging (LiDAR), to determine the relative importance of multiple environmental, biotic and management factors affecting treefall rates and patterns. We report a mean biennial treefall rate of 8 trees or 12% ha-1, but with heterogeneous patterns of loss in both space and time. Throughout Kruger, the influence of elephant density on treefall was matched only by spatial variation in soils and elevation, and all three factors co-dominated park-wide treefall patterns. Elephant density was up to two times more influential than fire frequency in determining treefall rates, and this pattern was most pronounced for taller trees (> 2 m in height). Our results suggest that confining megafauna populations to protected areas, or reintroducing them into former or new habitat, can greatly alter the structure and functioning of the host ecosystem. Conservation strategies will need to accommodate and manage these massive ecological changes in the effort to save megafauna from extinction, without compromising system functionality.