Bottom note box.
Know Your Phrase - The Meanings and Origins For Phrases and Common Idioms > N-Letter Sayings
The origins of this idiom.
The meaning of this phrase.
Phrases and Idioms - The Meanings and History For Popular Idioms and Phrases | Use this handy list of phrases to search for more!
Something that is extremely difficult to find. Anything that's on the verge of being impossible.
Today, this phrase is typically said as "It's like trying to find a needle in a haystack." This is considered to be an extremely difficult thing to do, and rightly so. Finding a tiny needle in a big stack of hay, while not impossible, would take a considerable amount of time and effort. Hence, when people are having trouble finding things in modern times, they often say this phrase to indicate the difficulties they are having.

As for where the phrase originates from, I don't think it's entirely clear. My guess would be farmers because I imagine them working with stacks of hay the most out of anyone. That's just a guess though. Here's what is known: This phrase is written in a old book titled The Complete Works of Washington Irving, published in 1834. As you will see from the quote, this expression is already well-established at the time:

"If I want to find any particular article, it is, in the language of an humble but expressive saying, --
'looking for a needle in a haystack.'"

Of note, I should mention that this idiom is believed to go back to the 1600s, but I am unable to find a written recording of it from that century. The above quote is the earliest recording I could find.
* Do you honestly believe you're going to find my cellphone in that heaping mess you call a room? It'll be like trying to find a needles in a haystack, it's simply not gonna happen!
Note: The origins for most common idioms cannot be said with a certainty. What's provided are theories that may be plausible to how a phrase originated, but not necessarily so.

In addition, quotes that contain a phrase may be taken from old newspapers, poems, or books that were written centuries ago, but this by no means shows they originated from these. In all likelihood, if an expression is being used in a newspaper, it's probably already well known, and thus, from an older period of time.