Recent publications on herbivore-plant dynamics, particularly long-term exclusion studies, indicate the importance of megafauna to the maintenance of many natural habitats. Megaherbivores often play a keystone role in modern ecosystems, which conservationists must consider if they are to implement a systems-based approach. One proposed strategy, “re-wilding,” involves reintroducing herbivores to regions where now-extinct species once lived. Research assessing the effectiveness of such strategies should include both modern and paleoecological perspectives. Paleoecological data can offer spatial and temporal perspectives not possible with modern process studies, and can address the rate and extent of landscape change following a particularly dramatic example of selective extinction during the late Pleistocene. Paleoenvironmental proxies allow reconstruction of megafaunal presence and ancient fire regimes, and advances in stable isotope analysis allow reconstruction of diet and migratory patterns of extinct species. Better integration of modern landscape ecology and paleoecology offers significant contributions to future restoration efforts. Modern ecologists can offer direct experimental and observational evidence of the impacts of herbivore presence on the landscape; paleoecologists can contribute a broader spatiotemporal perspective. Whether or not megaherbivores will ultimately play a role in restoration efforts, an understanding of their impact and ecology is critical to the development of conservation strategies.