When was Shiva worshipped first? This question has no specific answer. The origin of the worship of Shiva is lost and what is left is the inference of few scholars. And the scholars themselves don’t agree on these inferences.
The earliest account of Shiva is found in the Rig Veda Book 1, 43. There is reference of Shiva again in Rig Veda Book II, 33 and VII, 46. He is mainly known as Rudra and ‘Puru rupa’ in the Rig Veda. Next reference is in Atharva Veda and here he is mentioned as Rudra, ‘NeelSikandin’ – with blue body, Pasupati, Mahadeva and numerous other names meaning destruction. Next major reference of Shiva is found in Yajur Veda.
Vedas describe him as a fierce god and a destroyer. Some verses in the Vedas mention him as lightning and there are verses which describe him as a peaceful god. But mainly Shiva is fierce god.
If we take a closer look at Shiva worship, we will realize that many of his qualities are closely related to nature. The worship of Shiva might have already been in existence when Vedic seers arrived. Perhaps Shiva was more close to nature than of what we know about him today.
A classic example is that of ‘lingam’ worship. The worship of ‘lingam’ existed in Prevedic society and this is proved from the phallic symbols excavated from Indus valley civilization. Lingam is also mentioned in Rig Veda Book VII.2. and X.99