Gas chromatography/mass spectrometry, proteomic and scanning electron microscopy with energy-dispersive X-ray spectroscopy (SEM/EDS) analyses of residue on a stone flake from a 49,000 year-old layer of Sibudu (South Africa) indicate a mixture of ochre and casein from milk, likely obtained by killing a lactating wild bovid. Ochre powder production and use are documented in Middle Stone Age South African sites but until now there has been no evidence of the use of milk as a binder. Our analyses show that this ochre-based mixture was neither a hafting adhesive nor a residue left after treating animal skins, but a liquid mixture consisting of a powdered pigment mixed with milk; in other words, a paint medium that could have been applied to a surface or to human skin. The significance of our finds also lies in the fact that it establishes the antiquity of the use of milk as a binder well before the introduction of domestic cattle in South Africa in the first millennium AD.