As per the Legends mentioned in Skanda Purana and Brahmanda Purana, Demon Tarakasura theft Amrutha Atma Linga which emerged out during Ksheerasagar Mathanam (drilling Ocean of Milk). Tarakasura wearing this Linga around his neck, with hi supernatural powers, he was unbeatable. Kumara Swamy son of Siva and Parvathi, who was the commander-in-chief for deities came face to face with Tarakasura in the war. Kumara Swamy used his Sakthi weapon to kill Tarakasura. Kumaraswamy repeatedly broke Tarakasura body into pieces and it was reunified again.
Lord Maha Vishnu advised Kumara Swamy to break shiva linga into pieces, only then the demon can be killed. Maha Vishnu also said that even after breaking the shiva linga, the pieces will try to reunite again. To prevent this reunion, all these broken pieces should be fixed in those places where they fall, by worshiping and building temples on top it.
As advised by Maha Vishnu, Kumara Swamy used his Agni weapon to break the Siva Linga worn by the demon. The Atma Linga broken into five pieces, the broken pieces tried to reunite by making the chant 'Aum'. To prevent this Indra, Surya (Sun), Chandra (Moon), Vishnu and Kumara Swamy worshipped the Linga's at the respective places. It is believed that Lord Vishnu installed the Siva Linga and Tripura Sundari (Parvati) here.
Another interesting story associated with this temple, A poor Brahmin Koushika who struggle a lot for his daily needs. Once his son Upaveeta asked his mother to prepare milk rice. Due to poverty, she asked him to pray for Bhimeswara. As advised by her mother, he sat right in front of Idol for the milk. Impressed Lord Siva created a milk pool with his Trishul Hence, the name Ksheerapuram and Palakolanu which later called by Palakollu.