While the oldest shoes discovered are 7-8kya, the evolution of foot bone structure points to shoe-wearing as long ago as 40kya [1], predating the Neolithic.
It is very likely that shoes predate floors and were worn for easier travel over rough terrain.