My question is specifically about the earliest times and location of the origin of Lord Shiva's legends.
What are the earliest recorded stories about him, do the legends of Shiva originate within traditional Hindustan (India) region or from further out areas like Iran or Tibet etc? What historical records and/or archaeological artifacts have been found?
Edit:
I did some reading up following Veneet's comments below, and the earliest artifact found comes from Mohenja-Daro - the Pashupati seal, dating from 2600–1900 BCE. Reading 2 Reading 3
Some further reading led me to Celtic god Cernunnos. His artifacts had been made further away, in ancient Thrace (near Turkey/Greece/Bulgaria). They also date later after the Mohenja Daro seal. 200BC-300AD as compared to Pashupati seal's 2600–1900 BCE. Does this suggest that worship of Shiva extended much further than today? Then it would be similar to how Buddhism extended far and wide, and then shrank to smaller pockets of worship.
A more clearer picture, found on Gundestrup Cauldron artifact, dating 200 BC to 300 AD, probably from Thrace, located at modern Southern Bulgaria, Eastern Greece and North-western Turkey.:
I for one, find the similarity between our Shiva and their Cernunnos to be bloody remarkable.
This article, section "The Horned God - Cernunnos, Shiva or Pashupati?", talks about this, and Lord Shiva's and Sanskrit's connection to Celtic Druidism.
Can anyone shed further light?