The nature and causes of the disappearance of Neanderthals and their apparent replacement by modern humans are subjects of considerable debate. Many researchers have proposed biologically or technologically mediated dietary differences between the two groups as one of the fundamental causes of Neanderthal disappearance. Some scenarios have focused on the apparent lack of plant foods in Neanderthal diets. Here we report direct evidence for Neanderthal consumption of a variety of plant foods, in the form of phytoliths and starch grains recovered from dental calculus of Neanderthal skeletons from Shanidar Cave, Iraq, and Spy Cave, Belgium. Some of the plants are typical of recent modern human diets, including date palms (Phoenix spp.), legumes, and grass seeds (Triticeae), whereas others are known to be edible but are not heavily used today. Many of the grass seed starches showed damage that is a distinctive marker of cooking. Our results indicate that in both warm eastern Mediterranean and cold northwestern European climates, and across their latitudinal range, Neanderthals made use of the diverse plant foods available in their local environment and transformed them into more easily digestible foodstuffs in part through cooking them, suggesting an overall sophistication in Neanderthal dietary regimes.