Utkalas were a tribe belonging to the eastern part of India. Ilasudyumna, the son of Manu had three sons. They were Utkala, Vinatasva and Gaya who enjoyed the territories of Utkala, an undefined western country and Gaya respectively. The three territories have sometimes been collectively designated in the Puranas as Saudyumnas. The Saudyumnas thus occupied the hilly tracts from Gaya to Orissa. The epic tradition connects the Utkalas with the Udras, Mekalas, Kalingas and Andhras. The Drona Parva of the Mahabharata establishes that Kama conquered the Utkalas along with the Mekalas, Paundras, Kalingas, Andhras, Nisadas, Trigarttas and Yahlikas. In Ramayana the Utkala country is associated with the Mekala and Dasarna countries. In sending his army of monkeys to the different countries in quest of Sita, Sugriva asked Susena to send his retinue among other countries of the south to Mekala, Utkala and Dasarna.

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.