I can't think of a possible scenario where one would tell another to cool his heels (the very first time). Even if you walk a lot, only your legs hurt a lot. Why particularly heels?
How did it come into existence?
The idea seems to be that your feet become hot with walking and that when you stop walking they, and in particular, your heels, cool down. Hence, the current meaning of having to wait. The earliest recorded use of cooling the feet in this way is dated 1576. Coole their heeles first appears in 1606, where it appears to refer to horses. It is first applied to people in Chapman’s translation of the Iliad published a few years later.
Historically feet and horses (hence “hooves*”) were the standard method of travel and it was obvious to all that feet/hooves became hot through muscular activity when walking.
OED (Phrases)
P.4. to cool one's heels (also †feet, †hooves [obsolete]): to rest, esp. after the feet have become hot with walking; (now usually) to wait, to be kept waiting.
1576 And nowe they will him coole his feete, He cloyde with yrons great. G. Whetstone, Ortchard of Repentance 61 in Rocke of Regard
1606 Many striuing to stretch beyond compasse shal so heate themselues on New-market-heath, that they shall be constrained to coole their heeles in New-gate. A. Nixon, Black Yeare sig. Dv
?1611 The soldiers all sat down enrank'd, each by his arms and horse That then lay down and cool'd their hoofs. G. Chapman, translation of Homer, Iliads iii. 340
After this last date, the phrase settled down to “heels” and other foot-related expressions became obsolete.
*For the terminally pedantic, as “hooves” do not heat up perceptibly, “Hooves” in fact referred to (or were metonymy for) the combination of the tensor branches of the suspensory ligaments, sesamoidal ligaments and suspensory digital flexor tendons.
Here is the entry for "cool one's heels" from Christine Ammer, The American Heritage Dictionary of Idioms, second edition (2013):
cool one's heels Wait or be kept waiting, as in I've been cooling my heels in the doctor's waiting room for at least an hour. This term originally meant to cool one's feet when they become hot from walking, and began to be used ironically for being forced to rest (or wait) in the early 1600s.
The accepted answer to this question reports that "Coole their heeles first appears in 1606, where it appears to refer to horses." Searches of the Early English Books Online data base of published works from the period 1475 to 1700, however, turn up two matches from 1602 and two others from 1606 of various forms of "cool their heels." None of these matches seems to have anything to do with horses, nor do any of the other twenty-five matches from the period 1612–1699 that I examined closely. There may indeed be another instance from 1606 that does refer specifically to horses, but, if so, it is the exception to the rule, rather than an earlier form of the expression that later gave way to a focus on human heels.
[[Followup note (July 27, 2024): Encouraged by Greybeard's recent answer, I ran Early English Books Online proximity searches for various spellings of "cool [one's] hooves" and obtained one match—from George Chapman's 1611 translation of the Iliad:
The souldiers all sat downe enrank't, each by his armes and horse, / That then lay downe, and cool'd their hoofes. And now th'allotted course / Bids faire-haird Helens husband arme: who first makes fast his greaues, / With siluer buckles to his legs: then on his breast receiues / The curets that Lycaon wore, (his brother) but made fit / For his faire bodie: next, his sword, he tooke, and fastned it / (All damaskt) vnderneath his arme: his shield then, graue and great, / His shoulders wore: and on his head, his glorious helme he set; / Topt with a plume of horses haire, that horribly did dance, / And seem'd to threaten as he mou'd. At last he takes his lance, / Exceeding big, and full of weight; which he▪ with ease could vse.
The odd thing about this result is that the accepted answer to the posted question above identifies Chapman's 1611 translation of the Iliad as the place where "coole their heeles" "is first applied to people." A search of the Google Books version of Chapman's 1611 translation turns up ten matches for "heeles" and three matches for "cool'd" or "cool" but none for "heeles" in connection with cooling.
As both Barrie England and Greybeard note in their answers, the earliest match for "cool [one's] feet" is from George Whetstone, The Rocke of Regard Diuided into Foure Parts** (1576):
But here no lawē nor right do rule, / N• vaileth threats nor crakes. / With boltes and shackles on his shins, / His loade & héeles he shakes. / Where late was golde, an yron chaine, / Do well beseeme the necke, / His wrystes in steade, of braslets braue, / With manacles be deckt, / And nowe they will him coole his féete, / He cloyde with yrons great, / For all his lawe, is glad to pay, / Yea more then that entreate.
The description here is of a prisoner shackled, chained, manacled, and "cloyde with yrons. To the extent that these encumbrances have the effect of cooling his feet, that result seems primarily attributable to the coldness of cold iron rather than to some notion that the prisoner is being made to wait to be seen by someone.
An instance that much more clearly suggests the sense of "cool one's heels" as Ammer describes it appears just five years later in John Fielde, "A Caueat for Parsons Howlet Concerning His Vntimely Flighte, and Seriching in the Cleare Day Lighte of the Gospell, Necessarie for Him and All the Rest of That Darke Broode, and Vncleane Cage of Papistes, Who with Their Vntimely Bookes, Seeke the Discredite of the Trueth, and the Disquiet of This Church of England" (1581):
Gregory the second did irritate the subiects of Leo the Emperour agaynst him. As 〈◊〉 assoyled Pypin and the rest of the Frenche, from their othe and alleageance to Childericke, whome hee made to trotte at his horse hecles three miles together. Phocas 〈◊◊〉 and a murtherer is by him lifted vp to an Empire, & he againe for recompence aduaunceth him to be Antichrist, by giuing him that which the other sought for to wit to be the vniuersall Bishop, which his predecessors condemned. Hildebrand that firebrand of hel, of whom al stories write shame, made Henry the fourth with his wife & Sunne to coole his feete, the space of three daies at his gate, before he would admit him to his presence, and yet that was by the 〈◊〉 of his whore.
The form "cool [one's] feet" appears to be significantly earlier than the form "cool [one's] heels" (which I cannot find examples earlier than 1602 for), but the former is no longer in idiomatic use.]]
Early matches for 'cool [one's] heels' in the Early English Books Online database
Following are the earliest twelve Early English Books Online matches for relevant juxtapositions of "cool" and "heels".
From a 1602 translation of Johann Oberndorf, The Anatomyes of the True Physition, and Counterfeit Mounte-banke Wherein Both of Them, Are Graphically Described, and Set Out in Their Right, and Orient Colours:
He therefore that hath bene trained vp in Cunning, and nimble Shifts, and Cousenings from his youth, and desireth to fill his bagge speedily, and withall to haue the ringing Name and Fame of a great and profound Phisition, let him take Order to make his Medicines at home in a Corner, or Seller, or at least giue it out, that they are so prepared by Himselfe, though he secretly buy them abroad at the Apothecaries; or let him haue alwaies at Hand one, or at the most two or three Medicines (if one of them be a Charme it is no matter, but all the better, wherewith let him promise Boldly, confidently, and peremptorily, without blushing any more then a blacke Dogge, that he will Cure all Diseases whatsoeuer.
For by this meanes he shall be sure to vtter his Wares at a dearer and higher rate, then Reason or Honestie would require, and to make a good round Market when other stand still and coole theyr Heeles.
From a 1602 translation of Johann Oberndorf, "A Short Discourse, or, Discouery of Certaine Stratagems, Whereby our London-Empericks, Haue Bene Obserued Strongly to Oppugne, and Oft Times to Expugne Their Poore Patients Purses":
His [the mountebank's assistant's] maner is, to scratch and clawe our Magnifico by the Elbow, and to tolle on the silly Patient, in this sort. (Syr) vpon my credit, this is an honest and simple-meaning Gentleman, if he say the word, you may be bold to build and write vpon it. He would not tell you an vntruth (I dare say and sweare too for a need) if he might gaine thereby an hundred pounds. Though he goe but plaine, yet his Reputation is good in the Towne and Countrey where he dwelleth. He is sought vnto farre and neare. He is acquainted with diuers Noble men, and great Personages, and hath accesse vnto them, and is admitted into Ladies Chambers, when your gay Doctors with their veluet Ierkins are shut out of Doores, to coole their heeles.
From Anthony Nixon, The Blacke Yeare Seria Iocis (1606):
Tydes shall this yeare mount beyond their boundes, insomuch as many striuing to stretch beyōd compasse shal so heate themselues on New-market-heath, that they shall be constrained to coole their heeles in New-gate, where they are no sooner arryued, but foure knaues in the cardes shall sodenly leape from out the bunch, and desperately be ready (as partners) to entertaine them. This black yeare threatens diuers and sundry sortes of Takers, for some one shall be desirous to be taken for wise, who is indeede Sapientum octauus. Some will bee glad to take bad Siluer of poore debtors, and a Bottle of Ale, when they cannot get a pottle of wine. Some shall take their neighbours bed for their owne: some the Maide for the Mistresse, especially in houses, where Virgo is so predominant with the Maister, and wants a Mistresse to looke, narrowly vnto her.
From a 1606 translation of Suetonius, The Historie of Ywelve Cæsars Emperours of Rome:
Being now, as he [Otho] was, privie and partie to all the counsels and secret dessignes of NERO: he to auert all manner of suspicion, that very day which NERO had appointed for the murdering of his mother, entertained them both at supper with most exquisite, and the kindest welcome that might be. Semblably, Dame POPPAEA SABINA, being as yet but the paramour of NERO, whom he had newly taken from her husband, and committed in the meane while unto himselfe upon trust for to keepe, under a colour of mariage hee received: And not content herewith that he alienated her hart from NERO and used her body, hee loved her so entirely, that he could not endure NERO himselfe to be his Corrivall. Certes, it is thought of a truth, that not onely the messengers who were sent to fetch her, came againe without her: but also that one time he kept NERO himselfe without dores standing there and cooling his heeles, with threates also and prayers intermingled, demanding his pawne which hee had left with him, but all in vaine. Whereupon after the said mariage broken and dissolved, sent out of the way hee was under a pretence of an Embassage into Portugal: Which course was thought sufficient for feare least his proceeding to any sharper punishment might have told tales abroad and marred all the play: howbeit as secretly conueied as it was, out it came and was made knowne by this Distichon.
From Henry Peacham, "Honos venalis," in Minerua Britanna or A Garden of Heroical Deuises Furnished, and Adorned with Emblemes and Impresa's of Sundry Natures (1612):
For now the golden time's returned back, / And all's kept vnder, by th' Athenian Cat, / Whose helpe, and favour, whosoere doth lack, / May coole his heeles, with Homer at the gate: / Such is our age, where virtue's scarce regarded, / And artes with armes, must wander vnrewarded.
From Theodore Herring, Panacea Christiana, or, A Christians Soueraigne Salue for Euery Soare Deliuered in Two Seuerall Sermons, and Now Digested into One Treatise (1624):
Therefore doth he absent himselfe for a moment, to endeere his presence, that wee might greete him with a double welcome, and not too easily forgoe what cannot be obtained, without great difficulty. The Spouse in the Canticles, suffers her Beloued to stand knocking without doores: though hee plead his locke were wet with the droppes of the dew: Open my Loue, my Doue, my vndefiled. The lazie fit was on her, loth shee is to stir out of her warme nest, there he must waite and coole his heeles. No sooner doth the Bridegroome out of a iust distast draw backe, but she comes to her selfe, sees her folly, casts off her lithernes, starts vp, forth of Doores she gets her; seeking, enquiring him whom her soul loued, she pursues him (as it were) with heu and cry, resolues neuer to giue ouer seeking (though beaten and buffeted blacke and blew) till shee haue found him; and then clasps hands about his necke, and will bee sure to hold him faster then her owne life.
From William Rowley, A Match at Mid-Night A Pleasant Comœdie (1633):
Widdow. Shall I tell thee, for this thou hast given him this cure, and he is past care, for old Bloodbound the Saw-monger, I writ to him, to meet me soone at ten in the darke, vpon the change, and if I come not by ten, he should stay while twelue, intimating something mystically, that to avoid surprizalls of other Rivals, I meane to goe from thence with him to lye at his house all night, and goe to Church with him i'th morning, when my meaning is onely knavery, to make my selfe merry, and let him coole his heeles there till morning.
From Thomas Heywood, The Royall King, and the Loyall Subject (1637):
Bawd. Your Worship's most lovingly welcome: let the Gentleman have attendance, and cleane linnen it he need any; whither would you, you rogue?
Clown. Marry I would after my Master.
Bawd. Thy Master? why is yon raggamuffin able to keep a man?
Clown. Ey that he is able to keepe a man, and himselfe too.
Bawd. Then that man must be able to pay for himselfe too, or else he may coole his heeles without if his appetite be hot.
From John Taylor, A Iuniper Lecture With the Description of All Sorts of Women, Good, and Bad: From the Modest to the Maddest, from the Most Civil, to the Scold Rampant, Their Praise and Dispraise Compendiously Related (1639):
I doe marvaile how you found out the way, for you are not able to stand, nor looke up with your eyes, nor yet speake a ready word for lisping and clipping the Kings Eng∣lish: I see your horse had more wit than you, you may thanke him, or else you had never found the way home; hee can tell when he has enough, but you, you drunken sot, you pisse-pot, know not when you have sufficient; thus to come home reeling & staggering, it is a shame for you, it were a good deede to shut you out of doores all night, and make you coole your Heeles, now your brains are so hot: out you Dosser head, shallow-braind companion: In the morning then you cannot rise, then your head akes, and are sicke, and are untoward to doe, or goe about any thing; then you promise never to drinke so much againe: ...
From Gad ben-Arod, ben-Balaam, ben-Ahimoth, ben-Baal, ben-Gog, ben-Magog, The Wandering-Jew, Telling Fortunes to English-men (1640):
Is this Beast mad (cried the Jew) that keepes this rapping in such hast? let him coole his heeles, and know better manners; who is it Ioculo?
From Bartholomew Faire or Variety of Fancies, Where You May Find a Faire of Wares, and All to Please Your Mind (1641):
But by the way, I'le tell you a tale of a precise puritan, who came in all hast from Lincolne to London, purposely to see the Faire, where he had never bin before, and coming out of newgate marget, through Christ-Church into the Cloysters, and elevating the snow bals of his eyes, he presently espyes the picture of Christ and his twelve Apostles, with the virgin Mary, and many other Saints departed; at which sight the very thought and strong conceit of superstation set such a sharp edge upon the pure mettle of his inflam'd zeale, that very manfully like a man of va'our, and son of mars, he steps to a stall wel stor'd with two-pany halberts, and woodden backswords, where having arm'd himselfe Capa Pea, (as he thought) he begins in a violent passion, to exclaime against the Idolatry of the times, that it was grown abominable; protesting that the whore of Babilon was crept into Christ Church, and that the good motions of the Spirit had brought him to owne, to make a sacrifice of those Idle Idolls, to his just anger and holy indignation, which begot no small laughter to the multitude, which throng'd about him, that put him into such a chafe, in so much that at the last, like Rosicleare, the Knight of the sunne, or Don Quixot, most furiously he makes an assault, and battery upon the poore innocent pictures, till the shopkeepers apprehending him had him before a Constable, who forthwith comitted my little hot furie to the stocks, where we will leave him to coole his heeles, whilst we take a further view of the Faire.
From Thomas Fuller, The Holy State (1642):
He [the court favourite] makes not Great men dance envidious attendance to speak with him. Oh whilest their heels cool how do their hearts burn? Wherefore in the midst of the Term of his businesse he makes himself a vacation to speak with them. Indeed some difficulty of accesse and conference begets a reverence towards them in common people (who will suspect the ware not good if cheap to come by) and therefore he values himself in making them to wait: Yet he loves not to over-linger any in an afflicting hope, but speedily dispatcheth the fears or desires of his expecting Clients.
Even in the earliest instances collected here, the element of unwilling, frustrated, and ineffectual waiting for an audience or a turn that may never come seems integral to the usage.
In my youth in 1970s England, the expression was meant to denote being sent to wait in a corridor/ to see the Headmistress after some bad behaviour in the classroom. As in "she was sent to cool her heels in the corridor by the teacher". It implied awaiting some chastisement, and was used in English School Stories from the early part of the 20th Century.e.g. The Chalet School series.