The earliest evidence of agriculture in the Horn of Africa dates to the Pre-Aksumite period (ca. 1600 BCE). Domesticated C3 cereals are considered to have been introduced from the Near East, whereas the origin (local or not) and time of domestication of various African C4 species such as sorghum, finger millet, or t'ef remain unknown. In this paper, we present the results of the analysis of microbotanical residues (starch and phytoliths) from grinding stones recovered from two archaeological sites in northeastern Tigrai (Ethiopia), namely Mezber and Ona Adi. Together, both sites cover a time period that encompasses the earliest evidence of agriculture in the region (ca. 1600 BCE) to the fall of the Kingdom of Aksum (ca. 700 CE). Our data indicate that these communities featured complex mixed economies which included the consumption of both domestic and wild plant products since the Initial Pre-Aksumite Phase (ca. 1600 to 900 BCE), including C3 crops and legumes, but also C4 cereals and geophytes. These new data expand the record of C4 plant use in the Horn of Africa to over 1,000 y. It also represents the first evidence for the consumption of starchy products in the region. These results have parallels in the wider northeastern African region where complex food systems have been documented. Altogether, our data represent a significant challenge to our current knowledge of Pre-Aksumite and Aksumite economies, forcing us to rethink the way we define these cultural horizons.