Scholars have dated the caves and their carvings to be earlier than the writings of the Natyashastra. Certainly these caves are the first specimens of dance scene. It is obvious that the tradition codified in the Natyashastra recognized the particular regional style known in eastern India. The Natyashastra speaks of regional varieties, particularly mentioning the existence of the eastern southern style known as the Odhra Magadha style which can be identified as the earliest precursor of the present Odissi dance.

With the rise of Hinduism in Orissa, in the 7th Century A.D. many impressive structures were erected. From the temples of the 7th Century to the latest in the 14th Century, dance does appear in all sculpture.

The Parasurameswar Temple built in the 8th Century has a number of sculptures in postures of the Tandava dance. Temples, such as the Vaital Deul, also have poses of Nataraja. It has been suggested by some scholars that sculptures made from the 11th century to the 13th century, were merely trying to create an impression of the rhythms of dance and not illustrating the actual movements of dance. However, it does reveal that the sculptor was a knowledgeable person illustrating chapters of the Natyashastra. In these sculptures, we find the charis portrayed, which have been discussed in the Natyashastra. By the time the Konark Temple was built, the style had been set and distinctive method of body manipulation is apparent.

Orissa is fortunate in having two manuscripts which illustrate the dance style accurately. The manuscript demonstrates the existence of a distinct regional style; and the local style that follows the Natyashastra in broad principles.

The most notable manuscript is the Abhinayachandrika of Mahesvara Mahapatra, which has a detailed study of the various movements of the feet, hands, standing postures and the dance repertoire. The acrobatic Karanas as well as the saktasya, the chakramandal and the gangavatarana are portrayed. A study of these manuscripts suggests the popularity of the Odissi dance during these centuries. Creative literature inspired the Odissi dancer and provided the themes for the dance. The Gita Govinda had the same strong influence on Orissa. In the 8th Century Shaivism gradually gave place to the Vaishnavism, the Radha-Krishna cult became the inspiration of the performing arts. The writings of the Gajapati Emperor Kapilendra, the songs of Upendrabhaj, and the innumerable lyrics composed by writers of the Bhakti cult have made a tremendous contribution to the literature of Odissi dancing.

The kings of Kalinga kept dancers for the temples as an essential part of temple ritual. The dance before the gods continued to be performed even when social sanction was withdrawn. Orissa is indebted to the Kings for keeping its dance-style alive through times of political unrest and social upheaval. The dances were passed down, in the case of Mahari (female temple dancers), from mother to adopted daughter and, in the case of Gotipau, from teacher to the dedicated boys. Lack of patronage made it difficult to continue the Gotipua dance tradition in the temples of Orissa, and financial duress drove the young Gotipuas to Jatra or roving theatre groups, while the Mahari (temple dancers) continued the tradition within the temples. They earned their living dancing interludes to dramatic acts; thus Odissi had begun its move from temple to stage.

Over the centuries, three schools of Odissi dance have developed: Mahari, Nartaki, and Gotipau. The Mahari tradition is the Devadasi tradition which is the use of women who are attached to deities in the temple. The Nartaki tradition is the school of Odissi dance, which developed in the royal courts. However, after the 17th century, Odissi declined to great levels, as at that time dancers were considered to be shameless. As a result of this, no one was ready to learn this dance. Dancing girls were considered to be little more than prostitutes, and the "Anti-Naach" movement of the British brought Odissi dance to near extinction.

Independence brought a major change in official attitudes toward Indian Dance. The few remaining Odissi dancers were given employment, and a massive job of reconstructing the Odissi dance began. There were a number of people who were responsible for the reconstruction and popularization of Odissi dance. The revival of Odissi can be credited to Kalicharan Pattanayaka who presented Odissi artists on the stage and encouraged others to follow suit. In the 1950s, Abhinaya Chandrika revitalized the entire dance form, with the help of sculpted dance poses found in temples.

The current form of Odissi is the product of a 20th century revival. Dedicated scholars and dance enthusiasts carefully researched manuscripts and studied the sculpture, painting and poetry of the region. They also met and observed the performances of the few existing performers, in order to revive and restructure Odissi as a unique classical dance style adapted to the requirements of formal stage presentation. Over the years Odissi has become one of the most popular classical dance styles.