Orissa was part of the ancient kingdom of Kalinga. It first grew prosperous through trade. Kalinganagar port developed as early as 300 B.C. Java, Sumatra, Borneo, and Bali all established relations with the kings of Kalinga. The Maurya king Asoka conquered and annexed the Kalingan kingdom in about 260 B.C..

Orissa regained its independence in about 100 B.C. under the local king Kharavela. He was a Jain, and perhaps the greatest of the Kalinga kings. His achievements in extending his empire and descriptions of his capital are recorded in an inscription in the Udayagiri caves near Bhubaneswar.

His exploits included military expeditions in which he defeated the king of the Deccan. After Kharavela, two separate areas in the north and centre of the Orissa region developed. Their names were Utkal (a land where the arts excelled) and Toshali. During this time, sea trade flourished, and Buddhism once again became a popular religion.

Two dynasties had a major effect upon the history of Orissa. The rule of the Kesaris (A.D. 600-1076) and the Gangas (1076-1435) saw the development of a style of temple architecture often referred to as Indo-Aryan. The temples in and around Bhubaneswar were built by the kings of the Kesari dynasty.
The founder of the Ganga dynasty, Choda Ganga (ruled 1076-1148), was a devout Hindu and a patron of art and literature. He built the great temple of Jagannath at Puri. The most famous ruler of the Ganga dynasty was Narasimha I (ruled 1238-1264). He was responsible for the construction of the temple of the Sun God at Konarak.

The Gangas became rich through trade and commerce and used their wealth to finance their temple-building. By the early 1400's, their power was already starting to decline. The Surya dynasty took control in 1435 and ruled Orissa until 1542.

During medieval times, Orissa had been powerful enough and remote enough to resist the Muslim invasions from the north in the 1200's. But for a time the Afghans held Orissa in the 1500's, and the powerful Mughals arrived as conquerors in 1592. The Mughal emperor Akbar annexed it in that year. With the decline of the Mughals in the 1700's, the Marathas occupied Orissa for a time until the British took it over.

In 1765, after the victory of the British military leader Robert Clive at Plassey, the East India Company acquired parts of Orissa. Cuttack and Puri came under British control in 1803. Many interior areas remained under princely rule, subject to the paramount authority of Britain (the United Kingdom), until India gained its independence in 1947.