The territory of Utkala has been narrated in various Puranas. Utkala appears in the Mahabharata in association with the countries of Odras, Mekala, Kalinga,Darsana and Andhras. Tradition associates the origin of Utkala which Vaivasvata Manu who finds mention among the kings of India. It is said that Ila-Sudyumna, of the ten sons of Manu, who became male and female alternatively, gave birth to Utkala, Gaya,Vinitasva and Puru. He distributed the portion of his territory received from Manu among his sons and the land which came under the sway of Utkala was known as Utkala. This geographical name has also found mention in the Ramayana and is considered by some scholars to be older than Kalinga. Utkala has found mention in Kalidasa’s Raghuvamsam as a neighbouring kingdom of Kalinga. The earliest epigraphic evidence of the extent of Utkala is gleaned from the Midnapur Plates of Somadatta, a feudatory of Sasanka. The name Utkala is not found thereafter in epigraphic records for a long time.

Towards the final quarter of the seventh century A.D., the name Utkala appears in Adhabhara plates of Mahanannararaja of Sasivamsa which includes Utkala in the early Somavamsi Kindgom of Kosala. This geographical name also occurs in the copper plate grants up to the times of the Gangas of Odisha and Palas of Bengal. During the reigns of Ramapala of the Pala dynasty and Chodaganga of the Ganga dynasty the whole territory now known as Odisha appears to have been designated as Utkala. From the records of these kings it appears that Karnadeva, the last Somavamsi king, was driven out from his throne by Jayasimha, a lieutenant of Ramapala, but he was reinstated by Chodaganga. Even now the name Utkala is applied to the whole of Odisha. The earliest capital of Utkala was Viraja as is evidenced by the Soro Copper Plates. This place has been identified with Jajpur where the shrine of Viraja still exists. Viraja has also been mentioned in the Bhauma copper plate grants. Guhadeva Pataka or Gudhesvara Pataka, mentioned as the capital of the Bhaumas, was situated in its immediate neighbourhood.