Wildlife population declines in Africa are widespread. However, species-specific population trends and dynamics in mammal community composition have rarely been described over long time periods. To describe population trends of 13 large herbivore species in Lake Manyara National Park (Tanzania) from 1959 to 2016 and to discover whether the herbivore community structure changed, we used general additive models and additional statistical methods to detect structural changes in the time series. Population dynamics were non-linear and population growth rates were not correlated with precipitation anomalies. Relatively steep population declines of three megaherbivores occurred during the 1980s and early 1990s, resulting in severe reductions in African elephant and buffalo populations and the local extinction of black rhinoceros. These declines coincided with reported peaks of illegal hunting of these species and expansion of agriculture at the periphery of the park. Population densities of elephant and buffalo seem to have stabilized in recent times, yet have not recovered to previous densities. In contrast, eight species (giraffe, zebra, waterbuck, wildebeest, warthog, impala, bushbuck, and baboon) have apparently fared well (similar or higher densities in most recent compared to first decade), despite having undergone substantial fluctuations over the past 58 yr. Population fluctuations in these species were likely caused by disease outbreaks, heavy bush encroachment, and reduced competition with buffalo. Possibly, declines in megaherbivore densities (mainly elephants) facilitated bush encroachment. Albeit grazers are still dominating in the herbivore community, the proportion of browsers is currently increasing, likely encouraged by dense vegetation in the shrub layer in large parts of the park. Overall, herbivore biomass density has declined by ~40% compared to the baseline estimate in the first decade of the time series. Our analyses and ancillary information provide evidence that this overall decline in the herbivore assemblage was triggered by human-induced reductions in megaherbivore population densities during the 1980s, either through excessive poaching, insularization of the park, or both. Likely, this had cascading and interacting effects on the vegetation structure and the herbivore assemblage. Thus, legacy effects of ineffective megaherbivore conservation efforts 30 yr ago are likely still affecting the ecology of this national park.