The human archaeological record changes over time. Finding such change in other animals requires similar evidence, namely, a long-term sequence of material culture. Here, we apply archaeological excavation, dating and analytical techniques to a wild capuchin monkey (Sapajus libidinosus) site in Serra da Capivara National Park, Brazil. We identify monkey stone tools between 2,400 and 3,000 years old and, on the basis of metric and damage patterns, demonstrate that capuchin food processing changed between ~2,400 and 300 years ago, and between ~100 years ago and the present day. We present the first example of long-term tool-use variation outside of the human lineage, and discuss possible mechanisms of extended behavioural change.