History of Nayagarh District, Odisha claims that it was established by Suryamani of Baghela Dynasty who had once arrived in Puri on pilgrimage, from the region of `Rewa` which is situated in Madhya Pradesh. It is said that he had constructed a fort at this area and adopted Tiger Head as the official symbol of the state. This district was made the capital by the ninth ruler of the Baghela Dynasty, `Bagel Singh` who reigned from 1480 till 1510. Consequently, this region came to be recognised as `Baghua Nayagarh`, in the memory of this very ruler. Bagel Singh was a follower of Vaishnavism who is said to have created tiny idols of Shree Vigraha Chaturdha Murty and placed the deities on the foothills of Balarama, inside a mud altar.

Raghunath Singh was the 12th king of this district who ruled from 1565 to 1595, after defeating King Mukunda Deva in Gohritikira, who finally died. Raghunath captured Baunsiapara, Sarankul and Odegaon following his attack on Ranapur. Eventually, the border area of Nayagarh-Daspalla was also captured from the ruler of Boudh. The Sunamuhin portion of Odegaon was forcefully taken away from the ruler of Ghumusar. A part of Banpur was also annexed. Prior to his death Raghunath Singh had classified his personal estate amongst three of his sons. His son Jadunath Singh received four `Khandagrams` which was referred to as `Khandapara`, while Harihar Singh was the recipient of Nayagarh. Their descendants continued ruling over Nayagarh District until the time it was invaded by the British Raj in the country.

Nayagarh District is home to numerable historical temples like Raghunath Temple, Nilamadhab Temple, Dakhinakali Temple, Dutikeshwar Temple, Gopinath Temple, Ladubaba Temple and so on.

Rulers of Nayagarh District are numerous and include: