"amorous play with the feet" [OED], 1944, from foot (n.). Footie in the same sense is from 1935.
Entries related to footsie
"terminal part of the leg of a vertebrate animal," Old English fot "foot," from Proto-Germanic *fōts (source also of Old Frisian fot, Old Saxon fot, Old Norse fotr, Danish fod, Swedish fot, Dutch voet, Old High German fuoz, German Fuß, Gothic fotus "foot"), from PIE root *ped- "foot." Plural form feet is an instance of i-mutation.
The linear measure was in Old English (the exact length has varied over time), this being considered the length of a man's foot; a unit of measure used widely and anciently. In this sense the plural is often foot. The current inch and foot are implied from measurements in 12c. English churches (Flinders Petrie, "Inductive Metrology"), but the most usual length of a "foot" in medieval England was the foot of 13.2 inches common throughout the ancient Mediterranean. The Anglo-Saxon foot apparently was between the two. All three correspond to units used by the Romans, and possibly all three lengths were picked up by the Anglo-Saxons from the Romano-Britons. "That the Saxon units should descend to mediæval times is most probable, as the Normans were a ruling, and not a working, class." [Flinders Petrie, 1877]. The medieval Paul's Foot (late 14c.) was a measuring standard cut into the base of a column at the old St. Paul's cathedral in London. The metrical foot (late Old English, translating Latin pes, Greek pous in the same sense) is commonly taken to represent one rise and one fall of a foot: keeping time according to some, dancing according to others.
In Middle English also "a person" (c. 1200), hence non-foot "nobody." Meaning "bottom or lowest part of anything eminent or upright" is from c. 1200. Of a bed, grave, etc., from c. 1300. On foot "by walking" is from c. 1300. To get off on the wrong foot is from 1905 (the right foot is by 1907); to put one's best foot foremost first recorded 1849 (Shakespeare has the better foot before, 1596); Middle English had evil-foot (adv.) "through mischance, unluckily." To put one's foot in (one's) mouth "say something stupid" is attested by 1942; the expression put (one's) foot in something "make a mess of it" is from 1823. To have one foot in the grave "be near death" is from 1844. Colloquial exclamation my foot! expressing "contemptuous contradiction" [OED] is attested by 1923, probably euphemistic for my ass in the same sense, which dates to 1796 (also see eyewash).