In 1938 American field archaeologist Luther Cressman of the University of Oregon found dozens of sandals below a layer of volcanic ash while excavating at Fort Rock Cave, located in a small volcanic butte approximately half a mile west of the Fort Rock volcanic crater in central Oregon. These sandals, named for the site where they were first found, were later reported from ancient deposits in several Northern Great Basin caves. They are the oldest surviving shoes.
"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 (based on dendrocalibrated radiocarbon ages). . . . 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" (http://pages.uoregon.edu/connolly/FRsandals.htm, accessed 06-24-2014).
Fort Rock sandals are preserved at the University of Oregon Museum of Natural and Cultural History in Eugene, Oregon. In June 2014 a color image of one of the earliest Fort Rock Sandals was reproduced by the National Geographic from their September 2006 issue at this link. The article stated that the sandal illustrated was worn by a native North American who lived in caves during the winter months and hunted in marshes in summer.
Cressman, Luther S. The Sandal and the Cave: The Indians of Oregon (1981).
In May 2014 Oregon Public Broadcasting (OPB) aired a documentary entitled Luther Cressman, Quest for the First People.
My thanks to Lisa Midlam for drawing my attention to the Fort Rock Sandals and for supplying most of the references that I used for this entry.