In 2008 Lucinda Backwell, Francesco d'Errico, and Lyn Wadley discovered bone implements in Middle Stone Age (MSA) deposits at Sibudu Cave, South Africa, confirming the existence of a bone tool industry for the Howiesons Poort (HP) technocomplex, circa 63,000 BCE to circa 57,000 BCE. The bone tools included two points, one of which is consistent with sewing needles, and the end of a polished spatula-shaped piece of the type used to work leather. When I wrote this entry in 2013 the sewing needle found at Sibudu Cave was the earliest known.
Backwell L, d'Errico F, Wadley L.. "Middle Stone Age bone tools from the Howiesons Poort layers, Sibudu Cave, South Africa," Journal of Archaeological Science 35 (2008)1566–1580. doi:10.1016/j.jas.2007.11.006