The prevailing view regarding the evolution of medicine holds that the emergence of settled agricultural societies around 10,000 years ago (the ‘Neolithic Revolution’) gave rise to a host of health problems previously unknown among non-sedentary foraging populations, stimulating the first major innovations in prehistoric medical practices. Such changes included the development of more advanced surgical procedures, with the oldest known indication of an ‘operation’ formerly held to consist of a Neolithic farmer from France whose left forearm had been surgically removed and then partially healed. Dating to around 7,000 years ago, this accepted case of amputation would have required comprehensive knowledge of human anatomy and considerable technical skill and has thus been viewed as the earliest evidence for a complex medical act. Here, however, we report the discovery of skeletal remains of a young individual from Borneo who had the distal third of their left lower leg surgically amputated, probably as a child, at least 31,000 years ago. The individual survived the procedure, living for another six to nine years before intentional burial within Liang Tebo, a limestone cave in East Kalimantan. This unexpectedly early evidence for successful limb amputation implies that at least some anatomically modern human foraging groups in tropical Asia had developed sophisticated medical knowledge and skills long before the Neolithic farming transition.