Humans Wore Shoes 40,000 Years Ago, Fossil Suggests:
A previous study of anatomical changes in toe bone structure had dated the use of shoes to about 30,000 years ago.Now the dainty-toed fossil from China suggests that at least some humans were sporting protective footwear 10,000 years further back, during a time when both modern humans and Neandertals occupied portions of Europe and Asia.
The fossils go back further than any sandal remains:
The first forms of protective footwear probably evolved from simple wrappings used to insulate the feet from snow and freezing temperatures, experts say.The oldest preserved shoe remains, dating to roughly 10,000 years ago from the western United States, are simple sandals woven of plant fibers.
[...]
In a previous study, Trinkaus found that shoe-wearing and barefoot human groups show characteristic differences in the size and strength of their middle toe bones.Consistent shoe use results in a more delicate bone structure, because footwear reduces the force on middle toes during walking.
In his latest study, this anatomical evidence allowed Trinkaus to date the origin of shoes to a period long before the oldest known shoe remains.