Vamana Purana

When naked Lord Shiva was wandering in the Daruvanam forest, the wives of sages lost self control for Lord Shiva was the most beautiful and attractive man and they at once were seduced by the Lord.  The sages who failed to recognize the Lord thought he was an ordinary immortal and cursed him: May the Lingam (penis) of this man fall to the ground! That instant the Lingam of Shiva fell to the ground, and the God immediately disappeared. The Lingam, as it fell, penetrated through the earth to the lower worlds and increased in height until it towered above the heavens.  The earth quaked, all things movable and immovable agitated.  Brahma and Vishnu then decided to find the ends of the great Lingam, while Vishnu mounted on Garuda descended down and Brahma on his lotus ascended the heavens. They returned to where they started unable to find the ends of the great Lingam, and with great reverence and praise they requested Lord Shiva to resume his Lingam. Lord Shiva thus propitiated appeared and said: If gods and men will worship, I will resume it. To this proposal Brahma and Vishnu and all other Gods agreed and since then the Lingam is worshipped by all.
 

Shiva Purana

On falling in consequence of the sages’ curse, the Lingam became like fire, and caused a conflagration wherever it penetrated; the three worlds were distressed, and as neither Gods nor sages could find rest, they hastened for protection to Brahma.  Having heard them relate all that happened, Brahma replied, “After having committed knowingly a reprehensible act, why say that it was done unknowingly? Every one shall reap the fruit of his good or bad actions, and the Lingam therefore shall not cease to distress the worlds until the God resumes it. Propitiate by adoration the mountain-born Goddess, and she will assume the form of Yoni (vagina) and receive the Lingam, by which means only it can be rendered innocuous.  After obtaining the consent of Parvati, form a vessel of eight kinds of leaves, place in it boiled rice and sacred plants, having it filled with holy water, consecrate with proper prayers and invocations, and with water repeating at the same time suitable prayers, sprinkle the Lingam.  After Parvati receives the Lingam in her Yoni, you erect and consecrate the form of Lingam in the Yoni. By worshipping it with offerings of flowers, perfumes and such things, by kindling lamps before it, and by singing music propitiate Maheswara and he will forgive you.” As per Brahma’s instructions, the Gods and sages sought the assistance of Parvati. Parvati received in her Yoni the Lingam and appeased its consuming fire.  In commemoration of this event the worship of Lingam was instituted.
 

Lainga Purana

Brahma said to angels, “When I sprang into existence, I beheld the mighty Narayana reposing on the abyss of waters, and, being under the influence of delusion, awakened him with my hand and addressed him: ‘who art thou that thus slumberest on this terrible ocean?’ Hari awoke dispelling sleep from his lotus eyes, looked upon me and then arising said, ‘Welcome, welcome O Pitamaha, my dear son!’ On hearing the first of the Gods speak, I confined within the bonds of the quality of impurity, replied: why dost thou say, my dear son? For know me to be eternal god, the universal spirit, the creator, the preserver and the destroyer of the three worlds.’  He immediately answered, “Hear the truth, Oh four faced! And learn that it is I who am the creator, the preserver, and the destroyer, how canst thou forget Narayana the self-existent and eternal Being?’ hence arose terrible combat amidst the waters of the deluge, where to appease the contest and recall us to our senses, appeared a Lingam blazing like a thousand suns. Bewildered by its radiant beams, Hari thus said to me lost in amazement, ‘I will proceed downwards in order to ascertain the termination of this wondrous column of fire, do thou, O lord, proceed upwards and seek for its top.’ Having thus spoken he assumed the form of a boar, and I that of a swan, and we both proceeded in our search for four thousand years, but being unable to ascertain its termination, we then returned back wearied and disappointed. Thus still under influence of delusion, we prostrated ourselves before the Lingam, and were reflecting on what it could be. Then we heard a voice saying Om, Om, Om- and shortly after appeared Shiva in the midst of that column of fire. In commemoration of this event therefore was the worship of Lingam instituted.”
 

Scanda Purana and Visva-Sara-Prakasha

One day naked Mahadeva with a club in his hand chanced to pass by near a place where several sages were performing their devotions. Mahadeva laughed at them, insulted and provoked them with gestures and signs.  The sages cursed him and his Lingam or Phallus fell to the ground.  Mahadeva in this state of mutilation traveled over the world bewailing his misfortune and his consort Parvati ran after him singing mournful songs. (In Greek mythology this is called wanderings of Demeter and lamentations of Bacchus) The world thus stopped procreation and came to a standstill.  Gods and men searched for the sacred Lingam and found it grown to an immense size.  They cut it with hatchets into thirty-one pieces that became perfect Lingams. The Gods left twenty-one on earth and took nine to heaven and removed one to netherworld.

Shaivites insits that Kaba is one of the twenty-one places on earth. Arabian authors opine that Lingas were worshipped all over Arabia. According to many sources the first phallus was erected on the banks of Euphrates and was known as Balef-Wara-Linga.