Legendary account as found in the Skanda-Purana, Brahma Purana and other Puranas and later Odia litreture, state that Mahaprabhu Sri Jagannath was originally worshipped as Neela Madhab by a Sabar king ( tribal chief ) named Viswavasu. Having heard about the deity , king Indradyumna sent a Brahmin priest, Vidyapati to locate the deity, who was worshipped secretly in a dense forest by the tribal king Viswavasu. Vidyapati tried his best but could not locate the place. But at last he managed to marry Viswavasu's daughter Lalita .
At repeated request of Vidyapti, Viswavasu took his son-in-law blind folded to a cave where Neelamadhab was worshipped.
Vidyapati was very intelligent. He dropped mustard seeds on the ground on the way. The seeds germinated after a few days, which enabled him to find out the cave later on. On hearing from him , king Indradyumna proceeded immediately to Odra desha ( Odisha ) on a pilgrimage to see and worship the Deity. But the deity had disappeared .The king was disappointed .The Deity was hidden in sand. The king was determined not to return without having a darshan of the deity and observed fast unto death at Mount Neela, Then a celestial voice cried 'thou shalt see him '. Afterwards the king performed a horse sacrifice and built a magnificent temple for Vishnu. Narasingha Murti brought by Narada was installed in the temple.
During sleep, the king had a vision of Mahaprabhu Sri Jagannath. Also an astral voice directed him to receive the fragrant tree on the seashore and make idols out of it. Accordingly the king got the image of Mahabrabhu Sri Jagannath, Mahaprabhu Sri Balabhadra, Mata Subhadra and Chakra Raj Sudarshan Made out of the wood of the said tree and installed them in the temple.
Indradyumna's prayer to Brahma Dev :-
King Indardyumna put up for Jagannath the tallest monument of the world. It was 1,000 cubits high. He invited Brahma Dev, the cosmic creator, consecrate the temple and the images. Brahma came all the way from Heaven for this purpose. Seeing the temple he was immensely pleased with him. He asked him as to in what way can He (Brahma ) fulfill his (the king's ) desire, since HE was very much pleased with him for his having put the most beautiful Temple for Sri Vishnu.
With folded hands, Indradyumna said , " Bagwan, if you are really pleased with me, kindly bless me with one thing, and it is that I should be issueless and that I should be the last member of my family." In case anybody left alive after him, he would only take pride as the owner of the temple and would not work for the society.
Kanchi Aviyan :-
At one time, a king of Kanchi in the down south remarked that the king of Odisha was a chandala ( a man of very low caste or status) because, he performs the duties of a sweeper during the Car Festival . When this news reached the ears of the king of Odisha, he led an expedition to Kanchi. Before that, he implored the mercy of Mahaprabhu Sri Jagannath. The soldiers of Odisha marched towards Kanchi from Cuttack (the then capital city of Odisha, located on the banks of Mahanadi, at a distance of 30 Kms. from Bhubaneswar ) It so happened that when the soldiers, headed by the king Purusottam Dev, reached a place near the Chilika lake, a lady ,who was selling curd ( a milk preparation, sour in taste ) met him ( the king ) and presented a golden ring studded with precious gems and submitted . " Mahaprabhu, kindly listen to me. A little earlier, two soldiers riding over two horses ( white and black in colour ), approached me and said
'we are thirsty give us some curds ( ଦହି ) to drink.' I gave them curds. Instead of giving me money , they gave me this ring and said ,'the king of Odisha will come here, after some time , on his way to Kanchi. You present it to him and he will pay you the money.' So Maharaj, you take it and give me my dues. It took no time for the king to know that the ring belongs to Lord Jagannath. He was convinced that Sri Jagannath and Sri Balabhadra were proceeding to the battle field ahead of him to help him there. To perpetuate the memory of this great incident, the king founded a village in the Chilika lake area. As the name of the lady was "Manika" (ମାଣିକ), the name given to the village was "Manika Patana" ( ମାଣିକ ପାଟଣା ).Even to this day, the curds of this village are famous.