Before the rise of the Eastern Gangs the Nala dynasty had established a kingdom in Trikalinga region comprising parts of the modern districts of Bastar, Koraput and Kalahandi. The capital of the kingdom of the Nalas was at Pushkari. The Podagarh rock inscription indicates that pushkari was situated close to the site of Podagarh in Koraput district. The earliest known ruler of the Nala dynasty was Vrishadhvaja who is known from a seal discovered at Bhita. It is suggested that the seal was carried to Bhita when Bhavadattavarman, the grandson of Vrishadhvaja, went on piligrimage to Prayaga where he donated grants to Brahmins. The date of Vishadhvaja may be fixed from circa 400 A.D. to 420 A.D. The next king Varaharaja was probably the son of Vishadhvaja. He was a powerful and independent ruler and had a prosperous reign. Out of 32 gold coins of the Nala kings discovered at Edenga in Bastar district, seven large size and twenty-two smaller size coins belonged to Varaharaja. He had been assigned to the period from circa 420 to 440 A.D.
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 who has been identified with Narendrasena. The Bhakatakas capital Nandivardhana was occupied by the Nalas. Bhavadattavarman issued grants in favour of a Bhrahmin named Matradhyarya and his eight sons when he was at Prayaga with his queen. 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. But after sometime the Bhakatakas became very powerful under king Harisena who inflicted a crushing defeat on the Nalas. The Eastern Gangas rose to power in Trikalinga territory after the defeat and decline of the Nalas in that region.