पुराणों में इसे धरती का वैकुंठ कहा गया है। यह भगवान विष्णु के चार धामों में से एक है। इसे श्रीक्षेत्र, श्रीपुरुषोत्तम क्षेत्र, शाक क्षेत्र, नीलांचल, नीलगिरि और श्री जगन्नाथ पुरी भी कहते हैं। यहां लक्ष्मीपति विष्णु ने तरह-तरह की लीलाएं की थीं। द्वापर के बाद भगवान कृष्ण पुरी में निवास करने लगे और बन गए जग के नाथ अर्थात जगन्नाथ। यहां भगवान जगन्नाथ बड़े भाई बलभद्र और बहन सुभद्रा के साथ विराजते हैं। आओ जानते हैं भगवान नील माधव की कथा जो जगन्नाथपुरी से जुड़ी हुई है। यहां कथा वर्णन कई तरह या कहें कि भिन्न भिन्न रूप से प्रकट होता है।
प्रचीनकाल में मालवा प्रदेश में इंद्रद्युम्न नाम के एक राजा थे। जिनके पिता का नाम भारत और माता सुमति था। राजा विष्णुजी के परम भक्त थे। एक रात भगवान विष्णु ने उनको सपने में दर्शन दिए और कहा नीलांचल पर्वत की एक गुफा में मेरी एक मूर्ति है उसे नीलमाधव कहते हैं। तुम एक मंदिर बनवाकर उसमें मेरी यह मूर्ति स्थापित कर दो।
इस सपने के बाद राजा ने तप किया तो हनुमानजी ने प्रकट होकर उन्हें मंदिर के स्थान और उसके स्वरूप के बारे में बताया और कहा कि तुम पहले मंदिर बनाना प्रारंभ करो तो मैं इसमें तुम्हारी सहायता करूंगा। राजा ने ऐसा ही किया पुरी के समुद्र तट पर भगवान का भव्य मंदिर बनाया जिसमें उन्हें कई मुश्किलों का सामान करना पड़ा।
मंदिर बनने के बाद उसमें मूर्ति स्थापना करने का समय आया तो भगवान श्रीहरि ने पुन: सपना दिया और संकेत में कहा कि तुम कुछ लोगों को मेरे पवित्र विग्रह को ढूंढने के लिए भेजों। राजा ने विधिवत पूजा करने के बाद श्रेष्ठ मुहूर्त में अपने भाई विद्यापति सहित सभी लोगों को अलग-अलग दिशा में श्रीहरि के विग्रह को ढूंढने के लिए भेजा।
विद्यापति जिस दिशा में कमल का फूल लेकर चले उस दिशा में नीलांचल पर्वत के आसपास घने आम्रकानन जंगल और पहाड़ों की श्रृंखलाएं थी। विद्यापति एक ऐसी जगह गए जहां पर सबर नाम से आदिवासी जाती के लोग रहते थे। कबिले का मुखिया एक गुप्त स्थान पर जाकर भगवना नील माधव की उपासना करता था जहां पर नील माधव का विग्रह रखा हुआ था। वहां वह किसी को भी नहीं आने देता था। कबीले के सरदार की एक सुंदर लड़की ललिता थी, जिसने विद्यापति को जंगली जानवरों से बचाया था जो घायल हो गए थे।
वह लड़की ललिता विद्यापति को अपने घर ले आई और कबीले के सरदार जिसका नाम विश्ववसु था वह उसका पिता था। ललिता ने पिता को सारा किस्सा बताया कि यह व्यक्ति जंगल में भटक गया है और जानवरों ने इसे घायल कर दिया था तो मैं इसे यहां ले आई। विश्ववसु ने भी विद्यापति को आश्रय दिया और घायल विद्यापति का उपचार किया। विद्यापति ने दोनों को यह नहीं बताया कि मैं यहां किस उद्देश्य से आया हूं क्योंकि विद्यापति को पता चल गया था कि विश्ववसु और उसकी जाति के लोग ही भगवान नील माधव के विग्रह की पूजा करते हैं और अब मुझे जानना है कि वह विग्रह कहां रखा है।
बहुत दिन वहां रुककर विद्यापति कबीले के लोगों के बीच घुलमिल गया और एक दिन उसका विवाह कबीले के मुखिया विश्ववसु की लड़की से हो गया। फिर एक दिन विद्यापति ने अपने श्वसुर से नील माधव के दर्शन करने की इच्छा व्यक्त की। श्वसुर विश्ववसु ने शर्त रखी कि मैं तुम्हें वहां तक आंखों पर पट्टी बांध कर ले जाऊंगा। विद्यापति ने कहा कि पिताजी जैसा आप उचित समझे।
चतुर विद्यापति ने वहां जाते समय अपनी धोती में एक पोटली में राईं के दाने बांध लिए और जब उसकी आंखों पर पट्टी बांधकर उसे ले जाया गया तो रास्ते भर में उसने उन राईं के दानों को रास्ते में बिखेरता गया। अंतत: एक पहाड़ी की एक गुफा में जब उसके आंखों की पट्टी खोली गई तो उसके सामन प्रभु श्री नील माधव का विग्रह था जिसमें से तेज प्रकाश निकल रहा था। जिसे देखकर विद्यापति अति प्रसन्न हो गया।
फिर जब वे दर्शन कर लौट आए तो कुछ समय बाद जब वे राईं के दाने पौधों में बदल गए तो विद्यापति को वहां तक पहुंचना का मार्ग मिल गया। फिर एक दिन प्रात: जल्दी उठकर विद्यापति उस मार्ग पर जाने लगे तो उनकी पत्नि ने पूजा इतनी सुबह कहां जा रहे हो। विद्यापति ने कहा कि फूल एकत्रित करने जा रहा हूं ताकि भगवान को अर्पित कर सकूं और तुम्हारे लिए वैणी बना सकूं। यह सुनकर पत्नी प्रसन्न हो गई।
फिर विद्यापति वहां से सीधे नीलांचल पर्वत पर उसे गुफा में चले गए। शंका होने पर उनकी पत्नी भी उनके पीछे आ गई और उसने देखा कि विद्यापति तो प्रभु नील माधव की मूर्ति चुराकर ले जा रहे हैं तो उसे बड़ा दु:ख हुआ। विद्यापति ने अपनी पत्नी को सारा किस्सा बताया कि मेरे भाई राजा इंद्रद्युम्न हैं और उन्होंने एक भव्य मंदिर बनाया है जिसमें प्रभु की इच्छा से ही वह यह विग्रह स्थापित करना चाहते हैं। विद्यापति की पत्नी ने कहा कि मैं तुम्हें रोकने पर विवश होऊं और मेरे पिता यहां आए इससे पहले तुम यहां से चले जाओ। तुमने हमें धोखा दिया है, परंतु तुम मेरे पति हो तो मैं अभी कुछ और कहूं उसे पहले यहां से चले जाओ। विद्यापति निराश होकर वहां से चला जाता है।
विश्ववसु अपने आराध्य देव की मूर्ति चोरी होने से बहुत दुखी हुआ। उसने सोचा कि इस चोरी में मेरी बेटी ने भी विद्यापति का साध दिया है तो उसे अपनी बेटी को कबीले से निष्काषित कर दिया। उसकी बेटी उस वक्त गर्भवती थी। वह वहां से चली गई और एक गुफा में रहने लगी।
उधर विद्यापति विग्रह लेकर अपने भाई राजा इंद्रद्युम्न के पास लौट आया। राजा उसे देखकर प्रसन्न हुए और जब उन्होंने अपने महल में विग्रह को रखा तो उसे देखकर वे और भी प्रसन्न हुए परंतु श्रीहरि प्रसन्न नहीं थे क्योंकि उनके विग्रह को चुराकर लाया गया था। तब उन्होंने राजा को स्वप्न में कहा कि अब तुम मेरी मूर्ति बनाओ किसी श्रेष्ठ मूर्तिकार से। राजा ने कहा कि ऐसा मूर्तिकार कौन होगा जो आपका विग्रह बना सके।
भगवान ने कहा कि तुम मेरी मूर्ति बनाने के लिए समुद्र में तैर रहा पेड़ का बड़ा टुकड़ा उठाकर लाओ, जो द्वारिका से समुद्र में तैरकर पुरी आ रहा है। राजा के सेवकों ने उस पेड़ के टुकड़े को तो ढूंढ लिया लेकिन सब लोग मिलकर भी उस पेड़ को नहीं उठा पाए। तब राजा को समझ आ गया कि नीलमाधव के अनन्य भक्त सबर कबीले के मुखिया विश्ववसु की ही सहायता लेना पड़ेगी। सब उस वक्त हैरान रह गए, जब विश्ववसु भारी-भरकम लकड़ी को उठाकर मंदिर तक ले आए।
अब बारी थी लकड़ी से भगवान की मूर्ति गढ़ने की। राजा के कारीगरों ने लाख कोशिश कर ली लेकिन कोई भी लकड़ी में एक छैनी तक भी नहीं लगा सका। तब तीनों लोक के कुशल कारीगर भगवान विश्वकर्मा एक बूढ़े व्यक्ति का रूप धरकर आए। उन्होंने राजा को कहा कि वे नीलमाधव की मूर्ति बना सकते हैं, लेकिन साथ ही उन्होंने अपनी शर्त भी रखी कि वे 21 दिन में मूर्ति बनाएंगे और अकेले में बनाएंगे। कोई उनको बनाते हुए नहीं देख सकता। उनकी शर्त मान ली गई। लोगों को आरी, छैनी, हथौड़ी की आवाजें आती रहीं। राजा इंद्रदयुम्न की रानी गुंडिचा अपने को रोक नहीं पाई। वह दरवाजे के पास गई तो उसे कोई आवाज सुनाई नहीं दी। वह घबरा गई। उसे लगा बूढ़ा कारीगर मर गया है। उसने राजा को इसकी सूचना दी। अंदर से कोई आवाज सुनाई नहीं दे रही थी तो राजा को भी ऐसा ही लगा। सभी शर्तों और चेतावनियों को दरकिनार करते हुए राजा ने कमरे का दरवाजा खोलने का आदेश दिया।
जैसे ही कमरा खोला गया तो बूढ़ा व्यक्ति गायब था और उसमें 3 अधूरी मूर्तियां मिली पड़ी मिलीं। भगवान नीलमाधव और उनके भाई के छोटे-छोटे हाथ बने थे, लेकिन उनकी टांगें नहीं, जबकि सुभद्रा के हाथ-पांव बनाए ही नहीं गए थे। राजा ने इसे भगवान की इच्छा मानकर इन्हीं अधूरी मूर्तियों को स्थापित कर दिया। तब से लेकर आज तक तीनों भाई बहन इसी रूप में विद्यमान हैं।
वर्तमान में जो मंदिर है वह 7वीं सदी में बनवाया था। हालांकि इस मंदिर का निर्माण ईसा पूर्व 2 में भी हुआ था। यहां स्थित मंदिर 3 बार टूट चुका है। 1174 ईस्वी में ओडिसा शासक अनंग भीमदेव ने इसका जीर्णोद्धार करवाया था। मुख्य मंदिर के आसपास लगभग 30 छोटे-बड़े मंदिर स्थापित हैं। ब्रह्म और स्कंद पुराण के अनुसार यहां भगवान विष्णु पुरुषोत्तम नीलमाधव के रूप में अवतरित हुए और सबर जनजाति के परम पूज्य देवता बन गए।