The origin of its name is believed to be derived from a Savara chief called "Dhenka" who once ruled over the land. Unfortunately, concrete evidence documenting the prehistoric times of Dhenkanal is scarce, leaving its historical facts masked in uncertainty. Nevertheless, archeological findings and rock inscriptions shed some light on the early days of the district.
According to the Nasik rock inscription, the Sattavahana Dynasty ruled over the district during the 2nd Century A.D, followed by the Guptas in the 3rd and 4th Century A.D. The 6th and 7th Century A.D saw the rule of the Bhauma Karas, while the Sulki Dynasty ultimately took over and ruled until the 9th Century. Throughout the course of its history, the power of Dhenkanal has passed through the hands of various kings and chiefs, representing a multitude of dynasties.
Genealogically the following kings ruled over Dhenkanal.
| 1 | Hari Singh Vidyadhar – 1530-1594 AD | 2 | Loknath Ray Singh Bharamarbar- 1594-1615 AD |
| 3 | Balabhadra Ray Singh – 1615-1641 AD | 4 | Nilakantha Ray Singh- 1641-1682 AD |
| 5 | Nrusingha Bhramarbar- 1682-1708 AD | 6 | KunjaBehari Bhramarbar – 1708-1728 AD |
| 7 | BrajaBehari Bhramarbar- 1728-1741 AD | 8 | Damoodar Bhramarbar-1741-1743 AD |
| 9 | Trilochan Singh-1743-1785 AD | 10 | Dayanidhi Mohindra Bahadur – 1785-1796 AD |
| 11 | Ramachandra Mohindra Bahadur – 1796- 1807 AD | 12 | Krushna Chandra Mohindra Bahadur-1807-1822 AD |
| 13 | Shyamchandra Mohindra Bahadur – 1822-1830 AD | 14 | Bhagiratha Mohindra Bahadur – 1830- 1873 AD |
| 15 | Pitambar Deo-1873- 1877 AD | 16 | Dinabandhu Mohindra Bahadur-1877-1885 AD |
| 17 | Surya PratapMohindra Bahadur(Minor)- 1885-1905 AD | Surya Pratap Mohindra Bahadur- 1905-1918 AD | |
| 18 | Shankar Pratap Mohindra Bahadur-1918-1947 AD |