The birth history of Nayagarh, constitutes a significant phase in the political history of Orissa. As is depicted by the historical accounts of Nayagarh, the existence of the district is deciphered far back at the 13th century. Suryamani of Baghela dynasty came to Puri on a pilgrimage from "Rewa"of Madhya Pradesh and established his kingdom at Nayagarh. On their way to Puri, Suryamani and his brother Chandramani took rest at night at Gunanat. However Suryamani did not establish his kingdom by military campaigning, rather the goodwill of the local inhabitants was somewhat responsible behind that. As the conventional belief runs, the land where they were resting was infested with Tiger and at night, when a tiger attacked them, two brothers fought bravely and killed the tiger. With this incident the local people praised the brave brothers and elected Suryamani as their leader. Utilizing the goodwill of the local inhabitants, Suryamani built his fort there and married a local Mali girl. After the death of his first wife, he married a Kshatriya Girl. In this course of time he was engaged in the task of extending his empire and invaded Haripur and Ralaba. Following the historical records of Nayagarh district, the scholars have interpreted that during the reign of Suryamani the kingdom of Nayagarh was extended encompassing the major portion of Orissa.

The history of Nayagarh as believed by the scholars, is closely related with the mythological story associated with the district. Also according to some historians, the district owes all its historical significance from that mythological interest about the district. According to the ancient history of Nayagarh district, King Suryamani, while sleeping a tiger attacked him at Ralaba he again killed it in a brawl. At that very moment he saw a lady passing with an empty pot to fetch water. Astonishingly, she returned with a little boy. Immediately, Suryamani obstructed the way of that lady and wanted to know about the mystery. The lady told that she was Bouri Thakurani (a local worshiped goddess) and the tiger that the king killed was the boy. The lady even asked Suryamani to kill her and worship her as the presiding deity of his state. Right from that day, Goddess Bouri Thakurani is worshipped as the family deity of the king and he also built a fort in her name and considered the tiger head as the state symbol.

Ninth king of the same dynasty, Bagel singh selected and shifted his capital from Ralaba to a place, between Rukshi and Balaram mountains and this place was known as "Baghua Nayagarh" after his name. 12th king of the dynasty, Raghunath Sing (1565-1595) and also of Nayagarh was a powerful militant. As the history of Nayagarh relates, the district was completely under the Muslim influence during that time. The turmoil in the socio-political ethos completely demolished the social set up. Raghunath Singh then consecrated the throne of Nayagarh and competently handled the socio political condition. He attacked Ranapur and captured Odgaon, Sarankul and Baunsiapara area from Ranapur estate and evicted Nayagarh-Despalla boarder area from the King of Boudh and Sunamuhin area of Odgaon from the King of Ghumusar and established his sole authority over these vast areas. Raghunath Singh divided his kingdom among the three sons and Harihar Singh was in possession of Nayagarh. After him, the kingdom was passed on to several hands and when the British captured Orissa, according to the available historical records, Binayaka Singh was the King of Nayagarh.