It is an ancient locality in the middle part of India. In Matsyapurāṇa (Matsyapurana) it is described as a land adjacent to Vindhyaparvata (the mountain Vindhya). Ilā (Ila), daughter of Vaivasvata Manu, was transformed into a man and came to be known as Sudyumna. Utkala was one of the three valiant sons of Sudyumna. He was the ruler of this land, and the land came to be known after him
punaḥ putratrayamabhūt sudyumnasyāparājitam
utkalo vai gayastadvaddharitāśvaśca vīryavān.
utkalasyotkalā nāma gayasya tu gayā matā.
The great warrior Karṇa(Karna) once conquered the land of Utkala, on behalf of Duryodhana. The inhabitants of Utkala were also known as Utkala.
In Mahābhārata (Mahabharata) and Purāṇa (Purana), Utkala is sometimes mentioned as Uḍra (Udra), Oḍra(Odra) and Auḍra (Audra).