ओडिशा की कहानी लिखित अभिलेखों से बहुत पहले शुरू होती है, इसकी नदी घाटियों में मिले पाषाण युग के औज़ारों और तटीय मैदानों में शुरुआती खेतिहर बस्तियों के साथ। प्राचीन काल में यह क्षेत्र कलिंग के नाम से जाना जाता था, एक शक्तिशाली समुद्री प्रदेश जिसके व्यापारी श्रीलंका और दक्षिण-पूर्व एशिया तक जहाज़ ले जाते थे। लगभग तीसरी शताब्दी ईसा पूर्व में मौर्य सम्राट अशोक ने कलिंग पर आक्रमण किया, और कहा जाता है कि उस युद्ध के भयानक रक्तपात ने उन्हें बौद्ध धर्म और अहिंसा की ओर मोड़ दिया। उनके शिलालेख आज भी भुवनेश्वर के ठीक बाहर धौली में और दक्षिण में जौगड़ा में देखे जा सकते हैं।
मौर्यों के बाद महामेघवाहन वंश के राजा खारवेल के समय कलिंग फिर से उभरा, जिन्होंने लगभग पहली शताब्दी ईसा पूर्व में शासन किया। उनकी उपलब्धियाँ भुवनेश्वर के पास उदयगिरि और खंडगिरि गुफाओं के हाथीगुंफा शिलालेख में दर्ज हैं, जो जैन मुनियों के लिए तराशे गए शैलकृत कक्षों का एक समूह है। पास ही शिशुपालगढ़ के खंडहर उसी युग के एक बड़े किलेबंद नगर को सामने लाते हैं। यहाँ सदियों तक बौद्ध धर्म भी फला-फूला, और जाजपुर तथा कटक क्षेत्र में रत्नगिरि, ललितगिरि और उदयगिरि के मठ स्थल, जिन्हें अक्सर डायमंड ट्रायंगल कहा जाता है, घूमने के लिए बेहद सार्थक स्थान हैं।
प्रारंभिक मध्यकाल में शैलोद्भव, भौमकार और सोमवंशी सहित कई राजवंशों ने इस क्षेत्र के विशिष्ट मंदिर स्थापत्य को आकार दिया। भुवनेश्वर मंदिरों का नगर बन गया, और पर्यटक आज भी मनोहर परशुरामेश्वर और मुक्तेश्वर मंदिर तथा विशाल लिंगराज मंदिर देख सकते हैं। लगभग 11वीं से 12वीं शताब्दी में सत्ता में आए पूर्वी गंग वंश ने ओडिशा को उसके सबसे प्रसिद्ध स्मारक दिए। राजा अनंतवर्मन चोडगंग को पुरी के महान जगन्नाथ मंदिर के निर्माण का श्रेय दिया जाता है, और 13वीं शताब्दी में राजा नरसिंहदेव प्रथम ने कोणार्क का सूर्य मंदिर बनवाया, जो अब यूनेस्को विश्व धरोहर स्थल है और पत्थर के एक विशाल रथ के आकार का है।
15वीं शताब्दी से सूर्यवंशी परंपरा के गजपति शासकों के पास एक बड़ा राज्य था जो आज के ओडिशा से बहुत आगे तक फैला था। 16वीं शताब्दी के उत्तरार्ध में यह क्षेत्र बंगाल के अफ़ग़ान शासकों और फिर मुग़लों के हाथ में चला गया, और 18वीं शताब्दी में इसके बड़े हिस्से पर मराठों का नियंत्रण रहा। 1803 में ब्रिटिश ईस्ट इंडिया कंपनी ने इस पर अधिकार कर लिया। नई व्यवस्था के प्रति आक्रोश के कारण 1817 में बख़्शी जगबंधु के नेतृत्व में पाइक विद्रोह हुआ। 1866 में एक विनाशकारी अकाल पड़ा, और अगले दशकों में ओड़िया भाषा की रक्षा और ओड़िया भाषी क्षेत्रों को एकजुट करने के लिए एक मज़बूत आंदोलन खड़ा हुआ, जिसका नेतृत्व मधुसूदन दास और उनके उत्कल सम्मिलनी जैसी हस्तियों ने किया।
यह आंदोलन तब सफल हुआ जब 1 अप्रैल 1936 को उड़ीसा एक अलग प्रांत बना, और यह तारीख आज भी उत्कल दिवस के रूप में मनाई जाती है। ओडिशा ने स्वतंत्रता संग्राम में भी अपनी भूमिका निभाई, गोपबंधु दास जैसे नेताओं और तट पर इंचुड़ी के नमक सत्याग्रह के साथ। 1947 में आज़ादी के बाद मयूरभंज सहित इस क्षेत्र की कई रियासतों को 1948 और 1949 के बीच उड़ीसा में मिला दिया गया। राजधानी ऐतिहासिक नगर कटक से हटकर नए नियोजित भुवनेश्वर में आ गई, जिसे 1940 के दशक के अंत से पुराने मंदिर नगर के बगल में बसाया गया। 2011 में राज्य का नाम आधिकारिक रूप से उड़ीसा से बदलकर ओडिशा कर दिया गया।
यात्रियों के लिए ओडिशा का अतीत असाधारण रूप से सुलभ है। एक ही यात्रा में आप वहाँ खड़े हो सकते हैं जहाँ अशोक के शिलालेख खुदे थे, जैन गुफाओं में चढ़ सकते हैं, बौद्ध मठों के बीच घूम सकते हैं और पुरी में तीर्थयात्रियों को जुटते देख सकते हैं, और यह सब भुवनेश्वर से कुछ ही घंटों की दूरी पर है।