The quest for direct lines of evidence for Paleolithic plant consumption during the African Middle Stone Age has led scientists to study residues and use-wear on flaked stone tools. Past work has established lithic function through multiple lines of evidence and the spatial breakdown of use-wear and microscopic traces on tool surfaces. This paper focuses on the quantitative analysis of starch assemblages and the botanical identification of grains from flake and core tools to learn about human ecology of carbohydrate use around the Niassa woodlands, in the Mozambican Rift. The processing of starchy plant parts is deduced from the occurrence of starch assemblages that presumably got attached to stone tool surfaces by actions associated with extractive or culinary activities. Specifically, we investigate starch grains from stone tools recently excavated in northern Mozambique at the site of Mikuyu; which presumably spans the middle to late Pleistocene and represents similar sites found along the Malawi/Niassa corridor that links East, Southern, and Central Africa. Starch was extracted and processed with a diverse tool kit consisting of scrapers, cores, points, flakes, and other kinds of tools. The microbotanical data suggests consumption of seeds, legumes, caryopses, piths, underground storage organs, nuts, and mesocarps from more than a dozen families. Our data suggest a great antiquity for starch use in Africa as well as an expanded diet and intensification.