Prompted by a recent question about footwear, I decided to do some investigating on the origin of the term "shoelace." Securing footwear with leather thongs and cord dates back thousands if not millions of years. In fact, the earliest leather shoe ever discovered, in an Armenian cave in 2008, dates to 5,500 years ago and features this method of closure. (http://news.nationalgeographic.com/news/2010/06/100609-worlds-oldest-leather-shoe-armenia-science/)
Runaways in early America often wore shoes whose latchets (the straps crossing over the instep) were tied rather than buckled. Leather or cord ties were cheaper and sometimes more secure than metal buckles. Evidence from a number of archaeological sites, including several shipwrecks, indicates that shoe ties were also sometimes employed after the leather latchets had been broken by the metal teeth of a buckle. Before 1800, however, ties were generally referred to as "strings" rather than laces.
Merchants were advertising "shoe lace" as early as 1748 in the Pennsylvania Gazette. However, this term probably refers to the decorative trims used on ladies' shoes. A vendue sale advertisement in the New York Mercury on June 26th, 1768, included among a multitude of goods being auctioned "Women's plain and laces Shoes." In the eighteenth century, lace was a term used for a number of decorative woven materials which we might today refer to as braid, trim, or cord.
"Lace" also began to refer to shoe strings as early as 1801, when a notice for a "Dutch Servant Girl named Maria Leer" wearing "laced boots" appeared in Poulson's Daily American Advertiser of Philadelphia. When John Christian Hintzer ran away from his master, victualer Frederick Woelpper of Philadelphia, on May 19th, 1804, he was wearing "a pair of new laced shoes." A runaway slave named Frank had on "a pair of stout laced shoes" when he ran away from Gerrit Vanderveer of Flatbush, Long Island, on April 6th, 1806 (as advertised in the New York Republican Watch-Tower). Because these were individuals of the lower sort, and they were wearing work shoes, "laced" likely refers to a closure method rather than decorative trim.
It is probably no coincidence that "laced" as a term for thonged shoes became more popular just as the middling sort was adopting this style. By 1800, buckled shoes were rapidly falling from fashion. It is tempting to speculate, but impossible to know, that calling this new fashion "lace" added some bit of respectability to a style previously regarded as a mark of the lower sort.