सैकड़ों साल पहले उत्कल के महाराजा इंद्रद्युम्न ने एक विशाल मंदिर बनवाया था, परंतु उसमें स्थापित करने के लिए उन्हें मनचाही मूर्ति नहीं मिल रही थी। एक राज उन्होंने भगवान नीलमाधव को स्वप्न में देखा। भगवान नीलमाधव उत्कल की एक आदिवासी जाति सावरों के देवता हैं। राजा ने नीलमाधव को ही मंदिर में स्थापित करने का निश्चय किया। लेकिन किसी को भी नीलमाधव के मंदिर का पता नहीं था। इंद्रद्युम्न ने अपने महामंत्री विद्यापति को उसकी खोज में भेजा।

विद्यापति सावरों के सरदार विष्वबसु के पास गया और वहीं रहने लगा। कुछ समय बाद उसकी पुत्री ललिता से उसका विवाह हो गया। उसने एक दिन अपनी पत्नी से नीलमाधव के दर्शन की इच्छा प्रकट की। नीलमाधव का मंदिर तो घने जंगलों में था और कोई गैर सावर वहां जा नहीं सकता था। परंतु विद्यापति तो अब ललिता का पति था, सो उसे नीलमाधव के दर्शन की इजाजत मिल गई। तब भी उसकी आंखों पर पटृी बांधकर वहां ले जाया गया और दर्शन के बाद पटृी बांधकर ही वापस लाया गया। गहरे नीले पत्थर पर बने नीलमाधव के रूप को देखकर विद्यापति मंत्रमुग्ध हो गया। वह अपने साथ सरसों के बीज ले गया था। आते जाते समय वह बीज बिखेरता गया, ताकि उनसे दुबारा रास्ता पहचान सके।

कुछ समय बाद किसी बहाने से वह वहां से चला गया। आकर राजा इंद्रद्युम्न को सारी बात बताई। अब वे दोनों सरसों के बीजों की उपज का इंतजार करने लगे। फिर एक दिन सुनहरी सरसों के पौधों की दिशा में चलकर वे उस गुप्त मंदिर में जा पहुंचे। महाराज इंद्रद्युम्न भी नीलमाधव की मूर्ति देखकर मुग्ध हो गए। वहां पर रात को इंद्रद्युम्न ने दूसरा स्वप्न देखा। नीलमाधव ने स्वप्न में राजा से कहा कि, ‘हे राजा! इस गुप्त स्थान में रहते रहते मैं ऊब गया हूं। साथ ही नीलमाधव के रूप में पूजा भी अब अच्छी नहीं लगती। नीलांचल के निकट समुन्द्र में तुम्हें एक लक्कड़ तैरता मिलेगा। उसी से मेरी प्रतिमा गढ़वाकर अपने नए मंदिर में स्थापित करो और उसमें मेरी पूजा जगन्नाथ के रूप में होनी चाहिए।’

स्वप्न में संदेश के अनुसार समुन्द्र में बहता हुआ एक लक्कड़ तो मिल गया, परंतु कोई भी बढ़ई उससे नीलमाधव की प्रतिमा न बना सका। एक दिन अनंत महाराणा नामक एक बूढ़ा बढ़ई आया और उसने कहा कि मैं 21 दिन में मूर्ति बना सकता हूं, लेकिन उसकी एक शर्त थी कि इन पूरे 21 दिन तक उसे लक्कड़ और उसके औजारों सहित एक कमरे में बंद रखा जाए। इस बीच में कमरे को कोई न खोले।

बढ़ई की इच्छानुसार सारा इंतजाम किया गया। रोजाना राजा, मंत्री तथा अन्य सेवक कमरे के बाहर से आवाज सुन लेते कि अंदर काम हो रहा है। ठीक 21 दिन पूरे होने पर कमरे को खोला गया। परंतु वहां तो बढ़ई का नाम निशान भी नहीं था। केवल थी तीन मूर्तियां एक जगन्नाथ की, एक उसके भाई बलभद्र की और एक उनकी बहन सुभद्रा की। कहा जाता है कि शायद स्वयं नीलमाधव ने ही बूढ़े बढ़ई के रूप में आकर अपने हाथों से वे मूर्तियां बनाई थीं।

तभी से रथ यात्रा के अवसर पर तीनों मूर्तियों को तीन सजे हुए रथों पर रखकर जलूस निकाला जाने लगा।

महाराज इंद्रद्युम्न के सैकड़ों साल बाद पुरूषोत्तम देव उत्कल के राजा बने। वे श्री जगन्नाथ के बहुत श्रद्धालु भक्त थे। महाराज पुरूषोत्तम देव सारे राज्य को श्री जगन्नाथ की संपत्ति मानते थे और स्वयं को उसकी रक्षा के लिए नियुक्त एक तुच्छ सेवक, रथ यात्रा के अवसर पर पहले वे एक सोने की मूठ वाली झाडू लेकर रथों की सफाई करते थे, तभी रथों की यात्रा शुरू होती थी।

पुरूषोत्तम देव यह कार्य बड़ी श्रद्धा से किया करते। राजा पुरूषोत्तम देव ने एक बार उत्कल के दक्षिण में स्थित कांची के राजा को रथ यात्रा देखने का निमंत्रण भेजा। वह कांची की राजकुमारी पद्मावती को अपनी रानी भी बनाना चाहते थे। कांची महाराज भी कुछ कुछ इसके लिए तैयार थे। कांची महाराज राजमहल की अटारी से रथ यात्रा की तैयारी देख रहे थे। इतने में रथ तैयार हो गए और उत्कल नरेश झाडू लेकर नीचे उतर गए। नीचे जाकर उन्होंने रथों को अच्छी तरह झाड़ पोंछकर साफ किया। परंतु यह काम कांची नरेश को राजा के योग्य नहीं जंचा। उन्होंने रथ यात्रा से वापस आते ही उत्कल नरेश को संदेश भेजा कि वह एक चांडाल के साथ अपनी राजकुमारी का विवाह करने को तैयार नहीं हैं।

पुरूषोत्तम देव को यह अपमान सहन नहीं हुआ। वास्तव में उन्होंने इसे अपना ही नहीं भगवान श्री जगन्नाथ का भी अपमान अधिक समझा। उन्होंने इसका बदला लेने की ठानी और कांची पर आक्रमण कर दिया। लड़ाई में उनकी हार हुई।

अगली बार पहले उन्होंने देवताओं की आराधना की और फिर कांची पर आक्रमण किया। लड़ाई पर जाते हुए रास्ते में उन्हें एक गांव में मणिक नाम की एक ग्वालिन मिली। उसने राजा को बताया कि अभी कुछ देर पहले उनके दो सेनापति भी कांची की ओर गए हैं। एक सेनापति काले घोड़े पर सवार था और दूसरा सेनापति सफेद घोड़े पर। अपनी प्यास बुझाने के लिए उन्होंने उससे छाछ लेकर पी थी। पैसे न होने के कारण वे एक अंगूठी उसे दे गए थे कि जब महाराज उधर आएं तो उन्हें अंगूठी दिखाकर छाछ के पैसे ले ले। अंगूठी देखते ही उत्कल नरेश श्री श्री जगन्नाथ की अंगूठी को पहचान गए। वह समझ गए कि स्वयं भगवान श्री जगन्नाथ अपने भाई बलभद्र के साथ आगे गए हैं।

इस बार लड़ाई में विजयय प्राप्त करके पुरूषोत्तम देव राजकुमारी पद्मावती को बंदी बनाकर साथ ले आए।

उत्कल आकर उन्होंने घोषणा की कि पद्मावती के पिता ने मुझे चांडाल कहा था। इसलिए पद्मावती अब रानी न बनकर एक चांडाल की पत्नी बनेगी। महामंत्री यह राजाज्ञा सुनकर बहुत दुखी हुए। परंतु राजाज्ञा का पालन करने से वह इनकार कैसे करते? फिर भी उन्होंने गुप्त रूप से पद्मावती को अपने घर में अपनी पुत्री की तरह रख लिया।

अगली रथ यात्रा के समय महाराज पुरूषोत्तम देव सदा की तरह रथों की सफाई के लिए झाड़ू लेकर आए। उसी समय महामंत्री पद्मावती को लेकर उनके सामने जा खड़े हुए।

उन्होंने बड़े नम्र और संयत स्वर में महाराज से निवेदन किया, ”महाराज, आपने पद्मावती का विवाह एक चांडाल से करने की आज्ञा दी थी। अब आप से अधिक उपयुक्त चांडाल और कहां मिल सकता है। मुझे क्षमा करें और आप स्वयं अपने ही आदेश के अनुसार राजकुमारी से विवाह करके देवताओं का आर्शीवाद प्राप्त करें।“

महामंत्री की इस सूझबूझ से पुरूषोत्तम देव का क्रोध शांत हो गया और वे पद्मावती से विवाह करके सुखपूर्वक राज करने लगे।