प्रारंभिक स्रोतों के अनुसार, ओडिशा का समुद्री इतिहास 800 ईसा पूर्व से बहुत पहले शुरू हुआ था। बंगाल की खाड़ी के तट के साथ पूर्वी भारत के इस क्षेत्र के लोग भारतीय तट पर ऊपर-नीचे जाते थे और भारत चीन और पूरे समुद्री दक्षिण पूर्व एशिया की यात्रा करते थे। इस प्रकार वे अपनी संस्कृति के तत्वों से उन लोगों को परिचित कराते थे जिनके साथ वे व्यापार करते थे। छठी शताब्दी के मंजुश्रीमूलकल्प में बंगाल की खाड़ी का उल्लेख 'कलिंगोद्र' के रूप में किया गया है। इसी प्रकार प्राचीन भारत मे बंगाल की खाड़ी को कलिंग सागर के रूप में जाना जाता था। यह समुद्री व्यापार में कलिंग के महत्व को दर्शाता है।[1][2][3] पुरानी परंपराएं अभी भी वार्षिक बोइता बंदना त्योहार में मनाई जाती हैं। इसमें प्रमुख उत्सव कटक में महानदी के तट पर मनाया जाने वाला बाली जात्रा नामक प्रमुख उत्सव शामिल है। बाली यात्रा अक्टूबर-नवंबर में विभिन्न तटीय जिलों में सात दिनों के लिए आयोजित किया जाता है, हालांकि कटक में सबसे प्रसिद्ध है।