Residue analyses on a grinding tool recovered at Grotta Paglicci sublayer 23A [32,614 ± 429 calibrated (cal) B.P.], Southern Italy, have demonstrated that early modern humans collected and processed various plants. The recording of starch grains attributable to Avena (oat) caryopses expands our information about the food plants used for producing flour in Europe during the Paleolithic and about the origins of a food tradition persisting up to the present in the Mediterranean basin. The quantitative distribution of the starch grains on the surface of the grinding stone furnished information about the tool handling, confirming its use as a pestle-grinder, as suggested by the wear-trace analysis. The particular state of preservation of the starch grains suggests the use of a thermal treatment before grinding, possibly to accelerate drying of the plants, making the following process easier and faster. The study clearly indicates that the exploitation of plant resources was very important for hunter-gatherer populations, to the point that the Early Gravettian inhabitants of Paglicci were able to process food plants and already possessed a wealth of knowledge that was to become widespread after the dawn of agriculture.