It is popularly believed that the sacred temple of Srisailam exists from time immemorial. The significance of this sacred temple is emphasized by the fact that while we perform our daily household rituals we identify the place and location of our existence with reference to Srisailam. As per Agni Puranam, in Krithayuga, the Demon King Hiranyakasyapa performed penance at this temple and worshipped God Mallikarjuna Swamy. It is believed that this temple was his Puja Mandiram and the Ahobila Kshetram located at about 220 Km from Srisailam was his Sabha Mandapam.
According to Skanda Purana, in Trethayuga, Lord Sri Rama and Sita Devi during their exile visited this temple and sanctified Sahasra Lingas (One thousand Lingas) here.
The ancient scriptures narrate that in Dwapara Yuga, Pandavas during their exile and Arjuna while his pilgrimage spent some time in this temple to worship the Deities. There is a pond at the footway of Srisailam, which is called by the name Bheemuni Kolanu. It is believed that Bhagavan Dattatreya did penance at this temple. There a tree (Sthala Vriksham) in the temple complex, which is known as Dattatreya Vriksham.
In the present age of Kaliyuga, the great Advaita Philosopher Adi Sankara, Siddha Nagarjuna, Veerasaiva Saint Allama Prabhu, and Sivasarani Akka Mahadevi had visited this temple and worshipped the deities.