The noun clue appeared as a variant spelling of clew, of same pronunciation. Not frequent until the 17^th century, clue has become the prevailing form of the word in the sense of a fact or idea that serves to reveal something or solve a problem.

The word is from Old English cliwen, cleowen, meaning a ball formed by winding yarn, twine or thread (it is still one of the meanings of clew). Of Germanic origin, it is related to Dutch kluwen and German Knäuel, of same meaning. These three Germanic words are cognate with the synonymous Latin noun glomus (glomus is for glob-mus and is kindred with globus, the origin of English globe).

In Middle English, -ew was the normal form even for words from French such as blew, now spelt blue (cf. French bleu), and glew, now glue (cf. French glu). When these English words were in later times altered to -ue, this spelling was extended to various native words such as clue but also hue and rue.

Both the forms clew and clue were especially used to refer to the ball of thread employed as the means of ‘threading’ a way through a labyrinth or maze in various mythological or legendary narratives, the best-known being that of Theseus.

In Greek mythology, the Minotaur was a creature who was half-man and half-bull, the offspring of Pasiphaë and a bull with which she fell in love. (Pasiphaë was the wife of the king of Crete, Minos, hence the name Minotaur, the Greek ταῦρος (= tauros) meaning bull.) Confined in Crete in a labyrinth made by Daedalus, the Minotaur was fed with an annual tribute of seven virgins and seven young men from Athens. Theseus set himself the task of killing the Minotaur with the help of Ariadne, the daughter of Minos and Pasiphaë. She gave him a ball of thread, which he unravelled as he went in and used to trace his way out again after slaying the Minotaur.

The English poet Geoffrey Chaucer (circa 1342-1400) wrote about this myth in The Legend of Ariadne, from The Legend of Good Women (around 1385):

And for the hous is krynkeled to and fro,
And hath so queynte weyes for to go ―
For it is shapen as the mase is wrought ―
Therto have I a remedye in my thought,
That, by a clewe of twyn, as he hath gon,
The same weye he may returne anon,
Folwynge alwey the thred as he hath come.
     translation:
And because that dwelling-place winds much in and out, and has such intricate paths ― for it is shaped like a maze ― and for this I have in mind a remedy, that by means of a ball of twine he may directly return the way he went, following the thread continually.

Then, the word clue, or clew, was used in many more or less figurative applications to denote a fact, circumstance or principle which, being taken hold of and followed up, leads through a maze, perplexity, difficulty, intricate investigation, etc.

For example, the English poet and clergyman John Pomfret (1667-1702) wrote, in the poem On the Marriage of the Earl of A— with the Countess of S— (1699):

Her Judgment sure, impartial, and refin’d,
With Wit, that’s clear and penetrating, join’d,
O’er all the Efforts of her Mind presides,
And to the noblest End her Labours guides:
She knows the best, and does the best pursue,
And treads the Maze of Life without a Clue!

As the original image of a ball of thread used in a labyrinth was gradually forgotten and the literal sense of clew/clue obscured, the word eventually took the modern meaning of something that helps to solve a problem or unravel a mystery, its prevalent form being clue.

According to the Oxford English Dictionary (2^nd edition – 1989), this modern meaning is first recorded around 1665 (it would be in fact 1628-29) in Journal of a Voyage into the Mediterranean by the English courtier and natural philosopher Sir Kenelm Digby (1603-65). But this is a mistake, as the passage quoted by this dictionary is from a preface written in 1868.

The first recorded use of the word in its modern sense is in Logick: Or, The Right Use of Reason in the Enquiry after Truth (1724), by the English hymnographer, theologian and logician Isaac Watts (1674-1748):

When the Reader is passing over such a Treatise, he often finds a wide Vacancy, and makes an uneasy Stop, and knows not how to transport his Thoughts over to the next Particular, for Want of some Clue or connecting Idea to lay hold of.

The spelling clew was still in usage in this sense in the late 19^th century. The English historian Edward Augustus Freeman (1823-92) wrote, in The History of the Norman Conquest of England, its causes and its results (2^nd edition – 1870):

It is possible that we may here have lighted on the clew to the great puzzle of Cumbrian ethnology.