The ecology of Neanderthals is a pressing question in the study of hominin evolution. Diet appears to have played a prominent role in their adaptation to Eurasia. Based on isotope and zoo archaeological studies, Neanderthal diet has been reconstructed as heavily meat-based and generally similar across different environments. This image persists, despite recent studies suggesting more plant use and more variation. However, we have only a fragmentary picture of their dietary ecology, and how it may have varied among habitats, because we lack broad and environmentally representative information about their use of plants and other foods. To address the problem, we examined the plant micro remains in Neanderthal dental calculus from five archaeological sites representing a variety of environments from the northern Balkans, and the western, central and eastern Mediterranean. The recovered micro remains revealed the consumption of a variety of non-animal foods, including starchy plants. Using a modeling approach, we explored the relationships among microremains and environment, while controlling for chronology. In the process, we compared the effectiveness of various diversity metrics and their shortcomings for studying microbotanical remains, which are often morphologically redundant for identification. We developed Minimum Botanical Units as a new way of estimating how many plant types or parts are present in a microbotanical sample. In contrast to some previous work, we found no evidence that plant use is confined to the southern-most areas of Neanderthal distribution. Although interpreting the ecogeographic variation is limited by the incomplete preservation of dietary micro remains, it is clear that plant exploitation was a widespread and deeply rooted Neanderthal subsistence strategy, even if they were predominately game hunters. Given the limited dietary variation across Neanderthal range in time and space in both plant and animal food exploitation, we argue that vegetal consumption was a feature of a generally static dietary niche.