A number of legends have grown round Srisailam and its principal deities. Among them the most significant one is that Parvatha, son of Silada Maharshi is said to have performed penance, pleased Siva and made him agree to live on his body. This Parvatha assumed the shape of big Hill Sriparvatha and Siva lived on its top as Mallikarjuna Swamy.
According to one story Chandravathi,the ruler of Chandraguptha Patana situated near Srisailam on the opposite bank of the river Krishna ran away from her father who made amorous advances to her went up the hill and settled down there with few servants. One day she found that one of her cows standing above a natural rock formation resembling the Sivalinga and shedding its milk over it. The princess in dream was informed that the piece of the stone was a self-manifested Linga of God Mallikarjuna and took to worshipping it. This story is mentioned in the Skanda Purana. Two sculptures of the Prakara Wall of the temple also represent this story.
According to another story Sri,the daughter of a Rishi did penance, pleased Siva and got her name associated with the name of the Hill( Sailam ) which thereafter came to be known as Srisailam.