From
here:
"Since the early 1500s there have been similar expressions to describe things difficult to find: "like finding a needle in a meadow of hay" and "like finding a pin's head in a cartload of hay." In the mid-1800s the expression became "needle in a haystack.""
And from
here:
"needle in a haystack - impossible search for something relatively tiny, lost or hidden in something that is relatively enormous - the first use of this expression, and its likely origin, is by the writer Miguel de Cervantes, in his story Don Quixote de la Mancha written from 1605-1615. According to Bartlett's, the expression 'As well look for as needle in a bottle of hay' (translated from the original Spanish) appears in part III, chapter 10. 'Bottle' is an old word for a bundle of hay, taken from the French word botte, meaning bundle. Brewer (1870-94 dictionary and revisions) lists the full expression - 'looking for a needle in a bottle of hay' which tells us that the term was first used in this form, and was later adapted during the 1900's into the modern form."