Right from the early traditions Utkala was distinguished from Odra or Udra and the distinction seems to have been maintained throughout in ancient Indian literature and inscriptions. It is equally evident that it was distinguished from Kalinga as well, though a verse in the Vana parva of the Mahabharata seems to suggest that Utkala at one time formed a part of Kalinga.
The Raghuvamsa of Kalmasa, however, represents Utkala as an independent kingdom. The Brahma Purana has also suggested that Utkala and Kalinga were separate kingdoms. Ramacharitam has also distinguished Utkala from Kalinga in the eleventh century. Mahasivagupta Yayati had also distinguished Utkaladesa from Kalinga. According to the Raghuvamsa, the eastern boundary of Utkala seems to have extended to the river Kapisa and to the realm of the Mekalas on the west, with whom they are constantly associated, and who were inhabitants presumably of the Mekala hills.
In a Pali Cannon it has been mentioned that Utkalas were a tribe mentioned along with the Mekalas. Towards the south they extended till Kalinga. It has also been deduced from historical records that Utkala must have comprised the southern portion of modern Chotanagpur. It has been said that Utkalas were people of the eastern part of the country and they became immediately contiguous with the southern neighbours of the Suhmas who occupied roughly the modern districts of Bankura, Midnapore, Purulia and Manbhum.
In Markandeya Purana it has been stated that locates the Utkalas as inhabiting the Vindhya Mountain Ranges, along with the Karfishas, Keralas, the Uttamaranas and the Dasarnas. Roughly speaking, the Utkalas were indeed a Vindhyan people in as much as the Chotanagpur hills are just an extension of the Vindhya ranges.
As far as definite historical reference is concerned it can be said that there is hardly any mention of the Utkalas as a tribe. But in later inscriptions and literature there have been numerous references to Utkaladesa or Utkalavisaya, the country presumably of the Utkala people.
It has been referred in history that Narayanapala, an Utkala king had fled as the kingdom of the Utkalas were attacked by Prince Jayapala of the Pala Dynasty. It has also been recorded that King Devapala had eradicated the race of the Utkalas along with the pride of the Hunas and the conceit of the rulers of Dravida and Gurjara.