The African montane bamboo Yushania alpina provides both habitat and food for many species in the Albertine Rift region. In Volcanoes National Park (VNP), Rwanda, it is especially important as a key food resource for the Endangered mountain gorilla Gorilla beringei beringei and Endangered golden guenon Cercopithecus mitis kandti. We examined temporal and spatial variation in bamboo shoots regeneration and consumption by primates, monitored between 2013 and 2018 in 82 16-m plots located along transects in VNP. Our analyses revealed a decline in vegetative regeneration of bamboo in recent years, which is mirrored by a decline in bamboo shoot consumption by primates; but an increase in proportional intake. Local declines in regeneration are potentially due to high intensities of herbivory, decreased amounts of rainfall during growing seasons, and natural processes that form part of the life cycle of bamboo. Moreover, spatial variation in bamboo regeneration can be explained by elevation, as well as by stand-level variation in soil acidity, vegetation density, and the density of dead bamboo culms. We discuss the potential mechanisms underlying observed temporal and spatial variations and outline possible effects of a decline in bamboo regeneration for primates and other aspects of biodiversity in VNP.