The sthala puranam for this divya desam can be found in both the Brahmanada puranam and Padma puranam. The story of Tiruvikrama avataram of Lord Vishnu is very well known. Bali Chakravarti, who was known for his generosity was troubling the Devas, who eventually approached Vishnu for help. Lord Vishnu decided to use Bali’s waekpoint, his generosity, and came to this world as the son of Kashyapa rishi and his wife Athithi. He took on the form of Vamana murthi. In the course of time, this brahmachari went to Bali chakravarti and asked for gift of land which could be covered by his three steps. Bali Chakravarti agreed. The Vamanan then assumed the Viswaroopa and covered the entire earth with one step, the Heavens with the second and at the request of Bali put the third step on the head of Bali and pushed him to Pathala. It is said the Tiruvikrama avataram of Lord was at Tirukkoilur.
When this avataram took place, Mirukandu rishi, the father of Markandeya rishi was not at that place. When he heared about the avataram, he felt sad as he was not there to witness the glorious form of the Lord. He undertook severe penance wanting the God to appear before him in the same form. He visited many kshetrams such as Gaya, Badri etc. On the advise of Brahma, he come down to Krishnabadra river and reached Krishnapuri where Brahma had told he will get Perumal’s darshan. In the course of time, an old brahmin and his wife approached Mirukandu rishi and said he and his wife were very hungry and tired. The rishi, even though he knew he had no extra food, went in and asked his wife to somehow prepare food for the old couple. His wife Mithravathi prayed to thayar and somehow was able to feed the old brahmain and his wife, to their satisfaction. At the end the brahmin appeared in front of the rishi with Sangu and Chakra in his hands. The old couple were none other than Perumal and Thaayaar. Mirukandu rishi prayed to God to show him His Tiruvikrama roopa so that he who had missed it earlier could derive the divine satisfaction. His wishes were satisfied by Lord and gave the rishi the Tiruvikram darshan. The rishi requested Lord to continue to stay in this form at this place for ever, so that other devotees could also have the similar darshan.
Another story connected with this place refers to the atrocities committed by a rakshasa Pathala Kethu who lived here. He had earlier prayed to Brahma and obtained a boon that he would be invincible. Having attained this boon, he became arrogant and started troubling both Devas and Minis performing tapas at Krishnapuram. Hence the Devas and the Munis approached Lord Vishnu and requested his to rid Krishna kshetram of this rakshas. Lord Vishnu assured them that he would protect them and find a solution soon. In the course of time, a King by name Kusadwajan came to Krishnaranya kshetram. The munis performing tapas here noticed his and immediately knew it was due to Lord Vishnu’s grace they have the protection of the King. They informed the king about the asura and their trouble with him. The king promised them he would take care of the asura. At this time, form no where, a horse by name Kuvalayam appeared. It was Lord Vishnus gift to the king to perform the holy task of killing the asura. The king got on the horse chased the asura and killed him in Kavala rishi’s ashram as he was hiding there. Having completed the task, the king asked Kavala rishi for the sure path to attain moksha. Kavala rishi advised him to stay here at Krishna kshetram and worship Tiruvikrama and his wish would be granted. The King did the same and latter Lord Vishnu apeared before him and granted his wish.
It is also believed that Brahma came to Krishna kshetram (Tirukkoilur) and prayed on the banks of Krishnabadra river (now known as Pennai Aru). Lord Vishnu appeared before him as Tiruvikrama at this place and assured his that he would stay here in his Archa form, thus enabling the rishis and other devotees to have his darshan for ever.