The Puranas mention the dynasty of the Nalas ruling in South Kosala. According to the Vishnupurana as many as nine kings of this dynasty ruled. The south-eastern portion of Kosala, comprising the Bastar district and the adjoining territory, seems to have been their homeland.
Vyaghraraja of Mahakantaka, whom Samudragupta subjugated after Mahendra of Dakshina Kosala, probably belonged to the Nala dynasty. We have no knowledge of the subsequent history of the dynasty for about a hundred years when we get the evidence of three kings, viz. Varaha, Bhavadatta and Arthapati who flourished in that order.
Bhavadatta occupied the Vakataka capital Nandivardhana for some time. Vakataka Prithivisena II, however, soon retrieved the situation and the Nalas were again settled in Pushkari, their capital. Prithivisena II, then devastated the Nala capital Pushkari.
They suffered another disaster at the hands of Kirtivarman Chalukya. Later, when the Chalukya Kingdom was overrun by the Pallavas, the Nala kingdom again expanded. They occupied the kingdom of the Somavamshis and ruled till the ninth century AD when they were ousted by a branch of the Kalachuris of Tripuri.