There were 20000-year old footprints discovered in Australia [1], the estimated speed of these barefoot runners was comparable to olympic sprinters.

[1] https://www.nationalgeographic.com/history/article/20-000-ye...