Control of fire was a hallmark of developing human cognition and an essential technology for the colonisation of cooler latitudes. In Europe, the earliest evidence comes from recent work at the site of Cueva Negra del Estrecho del Río Quípar in south-eastern Spain. Charred and calcined bone and thermally altered chert were recovered from a deep, 0.8-million-year-old sedimentary deposit. A combination of analyses indicated that these had been heated to 400-600°C, compatible with burning. Inspection of the sediment and hydroxyapatite also suggests combustion and degradation of the bone. The results provide new insight into Early Palaeolithic use of fire and its significance for human evolution.