Vijayawada is known in mythology as Vijayavata, and is mentioned in some inscriptions as Rajendracholapura also. it is a famous place of pilgrimage on the river Krishna, and 'has a temple dedicated to Lord Siva in his aspect of Malleswara or Jayasena. The origin or installation of Kanaka - durga Devi at Vijayawada is unknown. She is said to be Swayambu or selfmanifest. She also takes the aspect of Chandi or destroyer of the demon Durgama who was causing havoc among the peace - loving inhabitants of Dakshinapatha.

          The installation of Vijayeswara is said to have been done by Arjuna, one of the Pancha Pandavas, to commemorate his victory with Lord Siva in the shape of Kirata or hunter. The place Vijayawada is surrounded by many hillocks and the most important of them is Seethanagaram, while the less important is called the Kanakadurga or Kanaka konda. On the southern side of the Kanakadurga temple, is a hillock with sculptures bearing inscriptions, indicating the names of Gods and Goddesses cut below them. Most of these figures are forms of the Goddess in her aspect of Durga, which are dealt with in the Mantra Sastras. Traditionally these hills were originally continuous and at the command of the Lord, they got separated, making enough space for the river Krishna to pass through.

         One of these hills is called Indrakila, which is a famous hill mentioned in the Mahabharata as the place where the Pandava hero Arjuna obtained from Lord Siva an important weapon called Pasupatastra. The aspect of Lord Siva who appeared before Arjuna for granting him the boon is Kirata or the hunter. Bharavi in his celebrated Kavya "The Kirtarjuneeya" has immortalized this. The temple of Vijayeswara is attributed to Arjuna to commemorate the event of obtaining Pasupatha. The shrine has the representation of this and many other events of the Mahabharata commemorated in sculpture. It is stated that, prior to the Kaliyuga, the sage Agasthya had named the Lord at Vijayawada as Jayasena.The Mahabharata hero Arjuna, who was a great wrestler or Mallayoddha, called the Lord as Malleswara. Thus famous Lord Siva so goes the legend, graces with his presence and blesses the town Vijayawada on the banks of the sacred Krishna River.

          There is an inscription in the temple, of the 9th century A.D., in the usual Telugu script. The inscription is strangely recorded from bottom upwards. Its purpose is to say that a certain Thrikoti Boyi or Trikoti Boyu, the son of Kaliyama-Boy of Pechchevada, set up the pillar as a commemoration of his own fame, in order to secure distinction for his race. The Thrikoti Boyi is identified in the inscription with a Guhyaka Yaksha, who in Dwaparayuga was directed by Indra to direct Arjuna to Indrakila hill, where Arjuna should worship the Lord Siva in order to obtain Pasupatha from him.

         Besides being a religious centre, Vijayawada is also the very centre of Andhra culture. The Chalukyas of Kalyan once conquered this place, and the famous Chinese Hu-yan-Tsang had visited this place in 639 A.D. when Buddhism was at its zenith.

         How the place got its name?
The legend is as follows: During their wanderings in the forest, the Pancha Pandavas came to Darukavana, where Vedavyasa met them, and told them that one of them should perform Tapascharya in praise of Lord Siva, and obtain from him, the Pasupatastra as a boon, so that they may easily conquer their enemies. Arjuna was chosen for this task and be betook himself to the top of the Indrakila hill (which is said to be the same as the Indrakila hill of Vijayawada) and was performing intense Tapascharya, with his arms upraised, and standing on one foot, and surrounded by the Pancha Agnis or five fires, with four artificial fires around him, and the fifth being the Sun God himself above him.

          Being pleased with the great Tapascharya of Arjuna, Lord Siva wanted to further test his sincerity, before granting him the desired boon, and therefore took the form of a Kirata or hunter. Parvati also dressed herself as a huntress and the Sivagana of the Lord also came in several disguises. Accompanied by all these, Lord Siva was hunting on the Indrakila bill, driving a wild boar in front of him.

         The wild boar came to the side of Arjuna, and Arjuna being a great warrior, took up his bow, and shot it with a single arrow. At the same time, Lord Siva who was following it also shot it with an arrow, and being struck by both the arrows, the boar fell down dead in the middle. Both the Lord and Arjuna claimed the boar as their kill, and a controversy arose between them, as to whom the boar should belong. Words led to physical quarrel shortly, and the Lord and Arjuna began to wrestle with each other. An experienced and powerful wrestler though he was, Arjuna was no match before the Lord himself, and was soon exhausted. Even in the midst of that desperate struggle, he never lost his one-pointedness of mind and devotion to the Lord.

         To invoke divine aid in his favor, he made a Shivalinga out of the earth, worshipped it, and offered prayers to it. He saw the flowers, with which he worshipped the Linga, as physically falling on the hunter before him and he thereupon realised that the hunter was none other than the Lord himself. The hunter immediately disappeared and the Lord appeared himself before Arjuna, in all HIS glory. Arjuna prayed to HIM and his prayer was granted, and Pasupathastra was given to him by Lord Siva, As a commemoration of this great event, Arjuna is supposed to have installed the Vijayeswara temple here, in the Indrakila hill.

        In the Indrakila there are several rock-cut temples. These were supposed originally to be ancient temples, but during the course of time, they were completely buried under debris. When quarrying for stone and road metal was done, they were revealed, and the rock-out temples were preserved as protected monuments.