African savannas are the last stronghold of diverse large-mammal communities, and a major focus of savanna ecology is to understand how these animals affect the relative abundance of trees and grasses. However, savannas support diverse plant life-forms, and human-induced changes in large-herbivore assemblages-declining wildlife populations and their displacement by livestock-may cause unexpected shifts in plant community composition. We investigated how herbivory affects the prevalence of lianas (woody vines) and their impact on trees in an East African savanna. Although scarce (<2% of tree canopy area) and defended by toxic latex, the dominant liana, (Apocynaceae), was eaten by 15 wild large-herbivore species and was consumed in bulk by native browsers during experimental cafeteria trials. In contrast, domesticated ungulates rarely ate lianas. When we experimentally excluded all large herbivores for periods of 8 to 17 y (simulating extirpation), liana abundance increased dramatically, with up to 75% of trees infested. Piecewise exclusion of different-sized herbivores revealed functional complementarity among size classes in suppressing lianas. Liana infestation reduced tree growth and reproduction, but herbivores quickly cleared lianas from trees after the removal of 18-y-old exclosure fences (simulating rewilding). A simple model of liana contagion showed that, without herbivores, the long-term equilibrium could be either endemic (liana-tree coexistence) or an all-liana alternative stable state. We conclude that ongoing declines of wild large-herbivore populations will disrupt the structure and functioning of many African savannas in ways that have received little attention and that may not be mitigated by replacing wildlife with livestock.