The temple is associated with a sage called Herandar who according to legend, is believed to have gone through an underground passage to the nether world and brought the Kaveri River to the earth to flow into the Bay of Bengal. Since the river took a convoluted direction in its flow, the place is called Tiruvalanjuzhi. There is an image of Herandar in the temple and the trunk of the elephant-headed god, Ganesha (Vinayagar) swirls towards the right. The presence of Buddhist images from the Chola period in the temple show influence of Buddhist tradition in the region.
The temple is renowned for its shrine dedicated to Ganesha (Vinayagar, Vinayaka). The idol of Vinayaka is white in colour and is believed to have been created out of sea sand. Hence, the temple is also known as Swetha Vinayagar Temple in Sanskrit or Vellai Vinayakar Temple in Tamil, meaning "the temple of the white Vinayaka".
According to popular legend, Indra, the king of the Devas created the idol of Ganesha out of sea sand during the churning of the ocean and left it in a niche in the temple hoping to get back the idol sometime later. But later, when he returned to remove the idol of Ganesha, it would not budge. So, the idol was allowed to remain where it was. A lattice-worked stone window pane called palahani is present in the temple. The temple is originally believed to have been built by Kanaka Chola in prehistoric times.