Archaeologists working at Areni-1 cave in Armenia have found one of the earliest known shoes and the first one of a kind that was common in parts of Europe until recently. This type of rustic shoe made of a single piece of leather tied with leather strings (or cords) above the foot is known as pampooties in Ireland and as abarka in the Basque Country.
The shoe, dated to 3627–3377 cal. BC, in the Chalcolithic Age, is roughly contemporary with other oldest findings of shoes across the World: the footwear of Ötzi, made of two different leather pieces, a slip-on shoe from the USA and a sandal found in Palestine. However footwear is known to have been used since much eralier, with anatomical evidence strongly suggesting a Middle Paleolithic origin. Because of the perishable nature of the materials used, no older shoes are directly known to us though.
Ron Pinhasi et al. First Direct Evidence of Chalcolithic Footwear from the Near Eastern Highlands. PLoS ONE 2010. Open access.
See also the article at the PLoS ONE blog, EveryOne.
Above: modern pampooties. From A brief history of World Costume, which has an interesting, albeit old, article on prehistoric clothing and footwear, including a reconstruction of Ötzi's footwear, similar to low boots.