It appears that the original image of Vishnu was worshipped on the spot where the great temple of Ananta Vasudeva was built in the 13th century A.D. Thus in the 13th century, Queen Chandrika of Eastern Ganga dynasty was prompted to construct a new temple - the temple of Anata Vasudeva in this place. There must have been an old temple where this Vishnu image was installed. The Marathas, who extended their empire up to river Mahanadi, were responsible for renovating the Vishnu temple at Bhubaneswar in the late 17th Century.
In form, the temple resembles the Lingaraj temple, but includes vaishnavite (Lord Vishnu related) sculptures. The temple has longitudinal bands of miniature shikharas (shrines), exactly like those in Lingaraj temple, with the minor difference that the number of the shikharas forming one longitudinal band in its case is only three. The sculpture in the exterior walls varies in character in each temple in Bhubaneswar. Most of the female sculptures in the temple walls are overly ornamanted and lack originality
The idols found in the garbhagrha (sanctum sanctorum) of the temple have complete structure unlike the images of the Jagannath Temple, Puri. Here the shrimurtis (idols) are made of black granite stone, rather than wood, as seen in the Puri temple. For this temple only the city gains its name as Chakra kshetra (circular place), whereas Puri is named Shankha kshetra (curved place).