Coca, of the genus Erythroxylum, is a stimulant and painkiller that played key roles within the Inka state. As reported by the early Spanish chroniclers, coca was the most important plant offering during public rituals. Likewise, important landmarks within the Inka domain regularly received offerings of this precious leaf. Its high value is indicated by the fact that not only the living chewed the leaves on a regular basis, but also the dead carried coca leaves in their mouths. We still do not know when coca leaves were first used in the Peruvian central highlands. This uncertainty is largely due to the lack of coca leaves recovered from highland archaeological sites. Several leaves recently found at Convento in the northern part of the Ayacucho Valley are the first direct evidence from an archaeological context that, based on ceramic stylistic grounds, dates to sometime between the end of the Early Intermediate Period (ca. 1-550 CE) and the beginning of the Middle Horizon Period (ca. 550-1100 CE). The botanical identification also indicates that the source of the coca was the Pacific coast. This paper reports this unique finding and discusses its implications.