The icon of Goddess Khambeswari in the form of Vanadurga is found in the temple. The earliest reference of the Goddess is found in the Terasinga Copper Plate of Maharaja Trustikara of 5th century A.D. Subarnapur was a very important stronghold of the cult of Khambeswari during the reign of the Bhanjas and the Somavamsis of 9th - 10th century A.D.

The temple of Khameswari at Subarnapur represents the most vibrant manifestation of this cult. It is said that the Khemidi princess during her marriage with Rajaraj Singh, the Chauhan ruler of Subarnapur had brought this icon of Khambeswari to the royal palace. Later on the Khambeswari temple was built by the king.