In Threthayugam, the second of the four yugas, people who enjoyed in heaven as a result of their good deeds in the world are most unhappy to return to this world (when once the fruits of good deeds are exhausted, the soul has to come back to the world). They prayed Indra, the Lord of heaven to save them from the impending fate.
Indra advised them to spend their time in the world at Mangalagiri to attain heaven again. In Krithayugam, the first of the four yugas when the sinners were few, Yamadharmaraja, the Lord of hell advised them to wash off their sins by doing penance at Mangalagiri.
Mangalagiri is in existence from the beginning of the Universe with the names Anjanadri in Krithayugam, Thotadri in Threthayugam, Mangaladri and Mukthyadri in Dwaparayugam and Mangalagiri in Kaliyugam affording salvation to sinners also. In Krithayugam, Vaikhanasa Maharshi worshipped the Lord and his idol is worshipped even today in the temple.
It is also believed that Lord Rama while departing for Vaikuntam after completing his mission in that incarnation advised Anjaneya to stay at Mangalagiri and after obtaining his blessings to remain in this world for ever. Anjaneya took his adobe at Mangalagiri as Kshetrapalaka.