In the Eurasian Upper Paleolithic after about 35,000 years ago, abstract or depictional images provide evidence for cognitive abilities considered integral to modern human behavior. Here we report on two abstract representations engraved on pieces of red ochre recovered from the Middle Stone Age layers at Blombos Cave in South Africa. A mean date of 77,000 years was obtained for the layers containing the engraved ochres by thermoluminescence dating of burnt lithics, and the stratigraphic integrity was confirmed by an optically stimulated luminescence age of 70,000 years on an overlying dune. These engravings support the emergence of modern human behavior in Africa at least 35,000 years before the start of the Upper Paleolithic.