This is a question better asked of /r/askanthropology. The mummified remains from Spirit Cave in Nevada, 9,400 BP (that's the c-14 date, which, when adjusted, looks more like 10,600 BP) included fur moccasins, which may be the oldest surviving foot wear in the world: that is, at least, what the archaeologists involved asserted. Reddit world may have older candidates. But suffice it to say, that the invention of footwear predates history, so this subreddit won't be the best place to ask your question.