The earliest known ruler of the Nala dynasty was Vrishadhvaja who is known to rule between 400 A.D. to 420 A.D. Next to ascend the throne was king Varaharaja who ruled from 420to 440 A.D. He was a powerful and independent ruler and had a prosperous reign.
Bhavadattavarman also called Bhavadattaraja was probably the son and successor of Varaharaja. During his rule there was conflict between the Nalas and the Bhakatakas and Bhavadattavarman defeated the Bhakataka king Narendrasena. The Bhakatakas capital Nandivardhana was occupied by the Nalas. He was a powerful and a generous king. He was succeeded by his son Arthapatiraja.
The Bhakataka king Prithvisena II, son of Narendrasena, defeated Arthapatiraja and ousted the Nalas from the capital Nandivardhana. He invaded Pushkari, the Nala capital, and destroyed it to a great extent. King Arthapati was probably killed in the battle. About 480 A.D. Skandavarman, the brother of Arthapatiraja, succeeded to the throne and restored the lost glory and prosperity of the Nala kingdom. However soon after this, King Harisen of Bhakataka inflicted a crushing blow to the Nalas. The Nalas could never recover from this defeat and their kingdom started declining.
There was a great resurgence of Vaishnivism under the patronage of the Nalas. Skandavarman who is known to be a devout Vaishnavite, had established a Vishu Vihar near Podagoda to promote the worship of Lord Vishnu.
Parvatadvaraka rule was established in the modern Balangir and parts of Kalahandi during the rule of the Nalas by King Sobhanaraja .The next ruler were Maharaja Tustikara who was a devoted worshipper of Goddess Stambhesvari. The capital Parvatadvaraka has been identified with Asurgarh in Kalahandi Not much, however, is known about this dynasty.
The Vigrahas and the Mudgalas
In the later half of the sixth century A.D. the South Kosala region came under the rule of the Sarabhapuriyas. By that time the Kalinga territory was divided into three parts. The South Kalinga with its capital Pishtapura was under the rule of the Durjayas, the middle Kalinga was under the Eastern Gangas, while the northern Kalinga known as Kalinga Rastra was being ruled by the Vigrahas.
To the north of Kalinga Rastra, extended the kingdom of Tosali which comprised of the districts of Baleshwar, Cuttack and Puri. It was divided into two units Uttara Tosali and Dakshina Tosali, the river Mahanadi being the dividing line. This kingdom was under the rule of the Mudgalas.
During the later half of the sixth century A.D. there was fight between the Mudgala King Sambhuyasa of Tosali and the Vigraha king Prithvi Vigraha of Kalinga Rastra. Prithvi Vigraha was succeeded by King Lok Vigraha as the Lord of Tosali at around 600A.D. He defeated the Mudgala King Sambhuyasa and annexed South Tosali. The victory was short-lived as Sambhuyasa was able to reorganize his army and defeat the Vigrahas in 603 A.D, thus reoccupying the lost kingdom.
During the mid 6th Century A.D., a chief named Ranadurjaya established his rule in South Kalinga with Pishtapura as his capital. The kingdom reached great heights under the rule of his grandson Prithvi Maharaja. He was able to establish supremacy over the Mudgals by annexing Tosali. He was subsequently defeated and driven out of his province by Sasanka who was able to retain parts of Kalinga to his kingdom.
During the later parts of 6th century A.D.Sailodbhava established a dynasty in the coastal regions of Orissa extending from Mahanadi in the north to Mahendragiri in the South. The territory was known as Kangoda mandala. After him Ranabhita also known as Dharmaraja I became the ruler. During later part of his rule, he was forced to act as a feudatory chief under the Vigraha king, Prithvivigraha.
He was succeeded by his son Madhavaraja who was a feudatory of the Vigraha king Lokavigraha. He was succeeded by Ayasobhita I alias Chharamparaja at a time when the political situation in the region was fluid with war going on the Vigrahas and the Mudgalas and Durjayas Taking advantage of the political situation Chharamparaja assumed independence.
However following the defeat at the hands of Sasanka in the year 615 A.D., his son and successor Madhavaraja II was forced to become a feudatory chief under Sasanka. Consequent to the death of Sasanka, Madhavaraja declared himself an independent monarch and in a charter to the public, called himself the Lord of entire Kalinga assuming the title of Madhavvarman.
At that time a great rivalry was ensuing between the Chalukya King Pulaksen II and Harshavardhan which helped Madhavavarman to maintain his independence. The situation did not change even after the defeat of Harsha by Pulakesin sometime before 634 A.D. But after the death of Pulakisin II in 642 A.D., the Chalukya power declined and Kangoda was occupied by Harshavardhana. Madhavavarman was once again forced to became the feudatory of Harshavardhana .However he declared himself free once Harsha died in the year 647 A.D., continuing to rule Kangoda till his death in 665 A.D.
He was succeeded by Madhyamaraja I who was somehow able to rule the region in perfect harmony .A religious person, he is known to have performed the Vajapeya and Asvamedha Yajna respectively. A war of succession between his sons Madhavaraja and Dharmaraja followed after his death. Madhavaraja was defeated in the battle of Phasika and Dharmaraja obtained the throne and performed his coronation. Meanwhile the defeated Madhava was able to garner the support of Tivaradeva, the powerful ruler of the South Kosala to invade Kangoda but the combined army of Madhava and Tivaradeva was defeated by Dharmaraja.