Three fragments of ostrich eggshell beads from the Late Acheulian of El Greifa E, Libya), similar to beads found at two Upper Palaeolithic sites in India. The site of discovery is Wadi el Adjal. There’s a modern example of this kind of bead to show how they are still worn.
Finally I found a solid reference and images of these beads. I’d heard of them in another paper, but I was starting to think someone had made them up. If the dating is accurate, they beat all the other contenders for the worlds oldest beads hands down. Except of course, for two items, drilled with stone tools, from the Repolust Cave, Austria (Bednarik 1992a: 34). They are thought to be almost 300,000 years old, although they could be beads or pendants. This would be a Heidelbergensis date for the Austrian pendants.
It seems that a fondness for personal adornment is something common to all humans, modern and archaic.