Around the period of the Norman Conquest a boot, also often spelt bote, was a thing that was advantageous, profitable or good (through the ancient Germanic languages, it’s closely linked with better and best as the comparative and superlative of good).
We still have it in the fixed phrase to boot, meaning something extra or additional; back around the year 1000 the phrase meant “to the good; to one’s advantage”. There were lots of meanings associated with boot: it might mean a levy taken to repair a road or bridge; in the feudal system it referred to the right of a tenant to take timber from his lord’s estate for fuel or repairs (a set of words existed for various kinds, such as firebote, housebote, and hedgebote).
It could also mean compensation for wrongdoing or injury. In this sense, it often appeared in compounds, such as man-bote, compensation by a person to somebody he had injured, or the later thief-bote, a bribe or reparations by a thief to avoid prosecution.
If you were bootless, you were without help or remedy or couldn’t be compensated. The meaning evolved into the figurative sense of something fruitless, unprofitable, or to no useful purpose. Charles Dickens used it this way in A Tale of Two Cities: “‘Well!’ said that good-natured emissary, after a full half-hour of bootless attempts to bring him round to the question.”
But the most famous example is probably that in Shakespeare's Henry IV in which the Bard puns on two senses of the word:
Glendower: Three times hath Henry Bolingbroke made head
Against my power; thrice from the banks of Wye
And sandy-bottom'd Severn have I sent him
Bootless home and weather-beaten back.
Hotspur: Home without boots, and in foul weather too?
How scapes he agues, in the devil's name.