New evidence has been uncovered that seems to date the habitual wearing of shoes back to at least 40,000 years ago. Just what that evidence is, the article doesn't really say. Just about the only thing it can be is some sort of skeletal change in the foot which is characteristic of wearing a shoe.