Early History of Odisha began from the pre historic time. The trace of the human civilization began from the Lower Paleolithic era. Kalinga has been mentioned in ancient texts like Mahabharata, Vayu Purana and Mahagovinda Suttanta. From early time, Odisha was named as Kalinga, Utkala, Mahakantara, Udra, Oddiyana, Kamala Mandala, South Kosala, Kongoda, Chedim, Tosali, Uranshin, Jajnagar and Odivissa.

Odisha in Purana
According to Purana, a king Bali, the Vairocana and the son of Sutapa, had no sons. So, he requested the sage, Dirghatamas, to bless him with sons. The sage is said to have begotten five sons through his wife, the queen Sudesna. The princes were named Anga, Vanga, Kalinga, Sumha and Pundra. The princes later founded kingdoms named after themselves. The prince Vanga founded Vanga kingdom, in the current day region of Bangladesh and some part of West Bengal. The prince Kalinga founded the kingdom of Kalinga, in the current day region of coastal part of Bay of Bengal- Odisha.

Mahabharata Era in Odisha
The Sabar people of Odisha have also been mentioned in the Mahabharata. It was the part of the Empire of Karna. Baudhayana mentions Kalinga as not yet being influenced by Vedic traditions, implying it followed mostly tribal traditions.

Kalinga War
Emperor Ashoka of the Mauryan dynasty conquered Kalinga in the bloody Kalinga War in 261 BC, which was the eighth year of his reign. According to his own edicts, in that war about 100,000 people was killed, 150,000 were captured and several more were affected. The resulting bloodshed and suffering of the war is said to have deeply affected Ashoka. He turned into a pacifist and converted to Buddhism.

Post Ashokan Era in Odisha
Emperor Kharavela in 150 BC who was possibly a contemporary of Demetrius I of Bactria, conquered a major part of India. He was a Jain ruler. He also built the monastery atop the Udayagiri hill. Subsequently, the region was ruled by the Jain such as Samudragupta and Shashanka. It was also a part of empire of Harshavardhana.

Somavamsi Dynasty
The kings of the Somavamsi dynasty began to unite the region of Kalinga. By the reign of Yayati II, they had integrated the region into a single kingdom. Yayati II is supposed to have built the Lingaraj temple at Bhubaneswar. They were replaced by the Eastern Ganga dynasty.

Anantavarman Chodaganga Dynasty
The notable ruler of Chodaganaga dynasty was Anantavarman Chodaganga, who began construction on the present-day Jagannath Temple in Puri 1135 AD, and Narasimhadeva I, who constructed the Konark temple in 1250 AD.