The tribal origin of Sree Jagannatha is coroborated by SKANDA PURANA, which is treated as authentic source material regarding the origin of Sri Jagannath worship at Puri and which devotes a full section running about 60 chapters called UTKAL KHANDA or PURUSOTTAM MAHATMYA in its second division -the VAISNAVA KHANDA. It says that Sree Jagannatha in the present form was installed by king Indradyumna of Malawa, who came all the way from that country with his family, ministers, priests, prominent citizens and a large contingent of army to pay a darshan to Nilamadhava which was being worshipped secretly by SAVARA CHIEFTAIN VISVAVASU in the form of a stone image. But he could not see Nilamadhava, who disappeared when Indradyumna, accompanied by Narada was coming to puri on the way.
''After Vishnu saved the world from the deluge in his varaha incarnation, Brahma asked him the means of salvation of all creatures. Vishnu said, 'I am being worshipped as Nilamadhava on the Blue hill in Purushottama kshetra. The highest form of salvation could be attained by beholding me there. This was a cause of apprehension to Yama, the god of ďeath, as he could not discharge his duties properly. On Yama`s request Vishnu assured him to disappear from blue hill. To fulfill his pledge given to Yama, Lord Vishnu made the shrine of Nilamadhava invisible under the sand''
Indradyumna was completly disheartened with the news, but sage Narada assured him that God would reappear in the form of Daru (a log of wood). Thus being consoled Indradyumna visited the Blue hill and offered ASWAMEDHA sacrifices there. On the closing day of the Aswamedha sacrifice Nilamadava appeared to Indradyumna in a vision,and at his bathing time the attendants came and informed him that a Daru with four branches was floating on the sea. The king with due ceremony brought the Daru and placed it on the Mahavedi. While discussing with Narada about fashioning the log into an image,the king heared a voice from heaven saying, ''God himself will make his own image .The aged carpenter standing with his tools should be shut up in a room for fifteen days and utmost secrecy should be maintained about the construction of image''. Things were arranged accordingly and at the end of the allotted time Sree Jagannatha, Balabhadra, Subhadra and Sudarsana appeared on the Mahavedi. Being directed by a voice from heaven the adorned the images with silken cloth and painted them with their respective colours. He also built a temple of one thousand cubits height to install the images.