Legendary account as found in the Skanda-Purana, Brahma Purana and other Puranas state that Lord Jagannath was originally worshipped as Neela madhab by a saver king (tribal chief) named Viswavasu. Having heard about the Deity, King Indradyumna sent a brahmin priest, Vidyapati to locate the Deity, who was worshipped secretely in a dense forest by 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 Vidyapati, Viswavasu took his son-in-law blindfolded to a cave where Neelamadhab was worshipped. Vidyapati was very intelligent. He dropped mustard seeds 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 (Orissa) on a pilrgimage to see and worship the Deity. The king was disappointed at the sudden disappearance of the Deity. The Deity was hidden in sand. The king was determined not to return without having darshan of the Deity and observed fast unto death at Mount Neela, when a celestial voice cried 'thou shalt see him'. Afterwards the king performed a horse sacrifice and built a magnificient temple for Vishnu. Narasinmha Murti brought by Narada was installed in the temple. During sleep, the king had a vision of Lord Jagannath. Also anastral voice directed him to receive the fragrant tree on the seashore and make idols out of it. Accordingly the king got Lord Jagannath, Balabhadra, Subhadra and Chakra Sudarshan made and installed them in the temple.