Accessing information on plant consumption before the adoption of agriculture is challenging. However, there is growing evidence for use of locally available wild plants from an increasing number of pre-agrarian sites, suggesting broad ecological knowledge. The extraction of chemical compounds and microfossils from dental calculus removed from ancient teeth offers an entirely new perspective on dietary reconstruction, as it provides empirical results on material that is already in the mouth. Here we present a suite of results from the multi-period Central Sudanese site of Al Khiday. We demonstrate the ingestion in both pre-agricultural and agricultural periods of Cyperus rotundus tubers. This plant is a good source of carbohydrates and has many useful medicinal and aromatic qualities, though today it is considered to be the world's most costly weed. Its ability to inhibit Streptococcus mutans may have contributed to the unexpectedly low level of caries found in the agricultural population. Other evidence extracted from the dental calculus includes smoke inhalation, dry (roasting) and wet (heating in water) cooking, a second plant possibly from the Triticaceae tribe and plant fibres suggestive of raw material preparation through chewing.