There is a common belief is in vogue that this Holy Kshetram exists from time immemorial.
The prominence of this Divya Kshetram is highlighted by the fact that while performing our daily household rituals we specify place and location of our existence with reference to Srisailam. According to Agni Puranam, in the Krithayuga the Demon King Hiranyakasyapa did penance at the Kshetram and worshipped God Mallikarjuna Swamy. This Kshetram was his Puja Mandiram and Ahobila Kshetram which is about 220 K.M. from Srisailam was his Sabha Mandapam.
The Skanda Purana proclaims that in the Trethayuga Lord Sri Rama with Seetha Devi during their banish has visited this Kshetram and consecrated Sahasra Lingas (One thousand Lingas) here.
The Epic literatures clear that in the Dwapara Yuga, Arjuna while his pilgrimage and the Pandavas during their exile spent some time in this Kshetram and worship the Deities. Even now there is a pond at the foot way of Srisailam called as Bheemuni Kolanu. It is also said that Bhagavan Dattatreya did penance at this Kshetram and at now also there a tree ( Sthala Vriksham) in the temple complex named a Dattatreya Vriksham.
In the Kaliyuga the Advaitha Philosopher Adisankara, Siddha Nagarjuna, Veerasaiva Saint Allama Prabhu, Sivasarani Akka Mahadevi spent some time at this Kshetram and worshipped the deities.