There used to live a bheel named Ahuk of the Arbudachal mountain. His wife was Ahuka. Both of them were supreme devotee of lord Shiva.
Once, lord Shiva wanting to test their devotion, appeared before them disguised a hermit. Ahuk honored his guest and treated him very well. Lord Shiva then requested him to give shelter for the whole night. Ahuk expressed his inability as he had a very small hut, in which only two people could be accommodate at a time.
But his wife intervened and requested Ahuk to sleep outside the hut with his arms, as it would be inappropriate on their part to miss this chance of proving their hospitality.
The hermit, who in reality was lord Shiva slept with Ahuk’s wife inside the hut, while Ahuk himself slept outside the hut. Unfortunately Ahuk was killed by a wild animal while he was asleep.
In the morning when lord Shiva found that Ahuk had died, his heart was filled with grief. But Ahuka consoled him by saying that she was proud of her husband as he had given up his life for a noble cause. Naturally she was very much saddened by her husband’s death so she decided to give up her life by jumping into the burning pyre.
Right then lord Shiva appeared in his real form and blessed her by saying-
“In his next birth your husband would take birth in a royal family. He would become famous as Nala and you would be born as Damayanti to king Bhima of Vidarbha. I would myself appear in the form of a swan and help both of you to unite. After enjoying all the pleasures of this world both of you would attain to may abode.
After saying thus, lord Shiva established himself as immovable Shivalinga, which later on became famous as Achaleshwar linga.