Originally, Jagannatha was worshipped as Nila Madhava by an aboriginal chief secretly at this spot, while it was covered with dense forest. It was Indradyumna, who made him a public deity. The story goes, there was a king in Malwa in central India, Indradyumna by name. He was a great devotee to Visnu. For those who are not acquainted with the names of Hindu gods and goddesses, it may be stated here that the Hindus believe in the cosmic trio namely Brahma, Visnu and Siva. Brahma is the creator of the universe, Visnu is the sustainer and Siva is the destroyer. Indradyumna developed in him a rather queer and eccentric desire to see Visnu in his most perfect form on the face of the earth. He had a divine communication in dream that Visnu could be seen in his best form in Utkala (another name of ancient Odisha). So, he deputed Vidyapati, the brother of the royal priest, to spot out the place where Visnu had such a manifestation and to report his findings to him. Accordingly, Vidyapati visited Odisha and after laborious search, came to know that Visnu known by the highly connotative name of Nila Madhava, was being worshipped somewhere on a hill in a dense forest. This was also an image of extraordinary lusture. Vidyapati could also know that Nila Madhava was the family-deity of Visvavasu, a Savara (an aboriginal tribe) chief. So great was the secrecy maintained about the location of Nila Madhava that Visvavasu refused on request to show Vidyapati the place of his worship. Later still, this Brahmin married Lalita, the daughter of the aboriginal chief, but even then, he was not shown the deity. At last, at the request of his beloved daughter, he took his son-in-law blindfolded to a cave on a hillock where Nila Madhava was being worshipped. As Vidyapati was made to go through the forest on foot, he could somehow manage to drop mustard seeds on the ground. As the seeds germinated after a few days, Vidyapati could easily trace the way to the lonely cave of Nila Madhava.
Thereafter, Vidyapati returned to Malwa and described his experiences to Indradyumna who immediately set out on a pilgrimage to Odisha. But, when he reached this holy land, he found that Nila Madhava had miraculously disappeared. When he was thus in a state of deep sorrow, he received a divine direction to go to the sea-shore at Puri and to draw ashore a log of wood that would be floating on the waves. From this divine log, the body of Jagannatha, who is no other than Visnu himself, was to be fabricated in a befitting manner. , All this came to pass as per the divine indication and a log of wood brought from the sea was ready for fabrication of the image of Jagannatha out of it. But there was none to be entrusted with the work, since nobody could say that he had seen Visnu and could convince the king as to how Visnu could be fabricated in his best form out of a log of wood. At last, Visnu took pity on his great devotee and appeared before him as an old carpenter. After some discussion, he could evoke confidence in the king about his capabilities. As per his suggestion; it was decided that he should be allowed to remain in a closed room with the log of wood for long twenty one days to do the needful. He gave a severe warning that under no circumstances should he be disturbed or the door be opened within the specified date. The story goes, after fifteen days, Gundica, the queen, being very kind-hearted, could not resist the temptation to persuade the king to open the door as she apprehended that the carpenter might have died by then, as, no sound of any kind was heard from within. Thus, when the door was opened at the king’s command, no trace of the carpenter could be found and all that could be seen was a set of four wooden images in incomplete form, i.e., the form in which we see and worship the images of Jagannatha, Balabhadra, Subhadra and Sudarsana at present.