Neatorama reader Doug suggested this link on my post on the 3,000-year-old shoes in Norway. Turns out, the Fort Rock Sandals are the oldest footwear ever found by man:
Fort Rock sandals are stylistically distinct. They are twined (pairs of weft fibers twisted around warps), and have a flat, close-twined sole, usually with five rope warps. Twining proceeded from the heel to the toe, where the warps were subdivided into finer warps and turned back toward the heel. These fine warps were then open-twined (with spaces between the weft rows) to make a toe flap. Cressman surmised that a tie rope attached to one edge of the sole wrapped around the ankle and fastened to the opposite edge.
Most dated Fort Rock-style sandals are from Fort Rock Cave, but directly dated sandals of this type are also known from Cougar Mountain and Catlow Caves. Directly dated Fort Rock style sandals range in age from at least 10,500 BP to 9200 BP
Link - Thanks Doug!