The greater bamboo lemur Prolemur simus is a Critically Endangered lemur endemic to eastern Madagascar. Wild P. simus populations have diets dominated by bamboo (Poaceae: Bambusoideae), particularly large-culmed species of two endemic genera, Cathariostachys and Valiha, but also of an endemic Arundinaria and the pantropical Bambusa vulgaris. A good understanding of the distribution and biology of large-culmed bamboos would, therefore, be a major help in understanding the factors influencing the distribution and conservation requirements of P. simus. During four years of research within the context of a collaborative programme aimed at conserving P. simus, we undertook surveys at 47 low-, mid- and high-elevation sites in eastern Madagascar between November 2008 and September 2012, covering a distance of over 1000 km from Makira in the north to Midongy in the south. We provide and illustrate characteristics helpful in the field identification, at least to generic level, of the large-culmed woody bamboos we encountered. The most frequently encountered non-endemic large-culmed bamboo was Bambusa vulgaris, with both the green and the yellow forms commonly planted in or near rivers, towns and villages. We made 1,343 georeferenced records of endemic, large-culmed bamboos, recording Cathariostachys from Makira to Midongy, Valiha diffusa from Makira to the southern parts of the COFAV, and Arundinaria from Zahamena to the COFAV. Valiha diffusa was recorded only at low elevations (9–576 m), and Arundinaria only at high elevations (1018–1667 m), while Cathariostachys was distributed across a wide range of elevations, from 53 to 1471 m, although most records were between 600 and 1,260 m. Valiha diffusa had the most variable culm diameters, ranging from 1.7 to 9.5 cm. Cathariostachys had the largest mean culm diameter of the endemic large-culmed bamboos (6.1 cm), and Arundinaria the smallest (4.0 cm). Culm diameters of Bambusa vulgaris were larger than those of the endemic bamboos, with a mean of 9.58. Cathariostachys had thinner mean culms at lowland compared to higher elevation sites. The revised distribution map we provide for Cathariostachys appears to correspond well to the potential current distribution of P. simus based on recent direct sightings, indirect feeding signs and unconfirmed local knowledge. Cathariostachys does not, however, currently occur throughout the historic range of P. simus. Valiha does occur at one P. simus subfossil site outside the current range, and therefore may have been the primary food source for the species there. Further research into the historical distribution of large-culmed bamboos in Madagascar would be very helpful in establishing how eventual changes in bamboo distributions over time may have affected changes in P. simus distribution.