According to the legend, Indrayumna, the king of Malava in Sata Yuga, was a great devotee of Vishnu. Once the king dreamt of Nilamadhava Vishnu and was curious to know where that particular form of the Lord was worshipped. Therefore, he sent his emissaries in four directions to find this.
Brahmin Vidyapati was sent to the east. He came to Utkala and entered Savara village where he took shelter in the house of the Savara King Visvavasu. Lalita, king's daughter, fell in love with Vidyapati and the latter got married to her to extract information about Nilamadhava.
Visvavasu used to go to the forest every morning to worship Nilamadhava installed in Niakandara (Blue cave). Vidyapati thus coaxed his wife to request her father to allow him to see Nilamadhava. Visvavasu agreed on the condition that Vidyapati will be taken to the shrine and brought back from there with a blindfold.
On hearing this, Vidyapati went to his wife and asked her to make such an arrangement that he may subsequently know the path. Lalita gave him some sesame seeds to be scattered on the side of the road he followed so that he might know the path when sesame plants grew up during the rains.
Accordingly, Vidyapati was taken to Nilakandara where he saw Nilamadhava. Later, when Vasu Savara offered food to the deity, he did not take it as usual to the king's dismay. At this, a divine voice was heard. It said, "we would no longer continue to be worshipped by you. Oh! Vasu, we will change the present Nilamadhava form and assume Daru form. We shall be worshipped in the temple by Raja Indradyumna".
The king came back from the blue cave with a very heavy heart losing his deity. Vidyapati too bade farewell to his wife and father-in-law and started for Malava. Having heard the story, King Indradyumna started with his retinue for Utkal to see Nilamadhava. On reaching Nilakandara, he found it vacant. But a voice from the air told him to construct a temple on Nilasaila (Blue Mountain).
Hearing this, the king ordered the construction to begin. On completion of the temple, the king went to Brahmaloka to invite Brahma to consecrate the temple. But, Brahma being in meditation, he had to wait for nine Yugas. The temple thus got buried in sand in his absence.
In the mean time, a new dynasty came to rule at Utkala. Galamadhva, a king of that dynasty, detected the buried temple. He was considering installing images in the temple when Indradyumna with Lord Brahma appeared before him. Both the kings had a tussle over the ownership of the temple. However, Lord Brahma decided in favor of Indradyumna and asked him to install deities in the temple.
Now, the king was at a loss as to where to find the deities from. Therefore, god told him in his dream that he would be floating in the sea in the form of a log of wood. Then Sage Narada assured Indradyumna that Vishnu would appear to him in the temple form of three wooden images.
When a big tree, radiant with light was seen floating in the sea, Narada told the king to make three idols out of it and place them in a pavilion. Indradyumna got Visvakarma, the architect of Gods, to build a magnificent temple to house the idols and Vishnu himself appeared in the guise of a carpenter to make the idols on condition that he was to be left undisturbed until he finished the work.
But just after two weeks, the Queen became very anxious. She took the carpenter to be dead as no sound came from the temple. Therefore, she requested the king to open the door. Thus, they went to see Vishnu at work at which the latter abandoned his work leaving the idols unfinished. But a divine voice told Indradyumana to install them in the temple.
The three idols represent the god Jagannath, his elder brother, Balabhadra and their sister, Subhadra. The wooden idols being worshipped are renewed during special occasions. This wooden idol prepared from a log of wood floating on the ocean finds a mention in the Rig Veda, where it is referred to as Purushottama.