The District of Nuapada was a part of Kalahandi District till early March 1993, but for the administrative convenience, Kalahandi District was divided into two parts i.e. Kalahandi and Nuapada vide State Government Notification No. DRC-44/93/14218/R. dated 27th March 1993. Nuapada District now comprises one sub-division (Nuapada), two tahasils (Nuapada and Khariar) and five Community Development Blocks (Khariar, Sinapalli, Boden, Nuapada and Komna).It is believed that the District of Kalahandi formed in ancient time a part of Mahakantara territory. During 4th century A.D.
when Samudra Gupta led his campaign through this region a king named Vyaghraraja was ruling over Mahakantara. After Vyaghraraja, the Nala kings like Bhavadatta Varman, Arthapati and Skanda Varman ruled over this region up to about 500 A.D.
In the 6th century A.D. a new kingdom developed in the Kalahandi tract under King Tustikara, but very little is known about other kings of his family.The Nuapada area was by that time under the kings of Sarabhapuriya dynasty whose copper plate record and gold coins are available. This region came under the occupation of the Somavamsis of South Kosala during the 8th century A.D. when Mahaivagupta Balarjuna was ruling from his headquarters at Sripur.
In the 9th century A.D. when the Somavamsis were ousted from the Sripur region and organized a new kingdom in Sonepur-Sambalpur tract, the Kalahandi portion continued to be under their rule. In fact, Mahabhabagupta Janamejaya occupied the Trikalinga territory (Koraput area) through Kalahandi. In the middle of the 10th century A.D. the Somavamsi dominion embraced the whole of Orissa under Yayati II Mahasivagupta. His son Udyotakesari divided this dominion and placed the western part (Kosala) under the rule of a collateral branch. Kalahandi was included in the Kosala kingdom the capital of which was Jajatinagar near Sonepur.
The rule of the Somavamsis in Kosala collapsed by the invasion of Rajendra Chola in 1022 A.D. and after that the territory came under the rule of the Telugu Cholas. In 1038 A.D. Vajrahasta V of Ganga dynasty became powerful in Parlakhemundi region and after the death of Rajendra Chola in 1044 A.D. he assumed independence and occupied the hilly territory including Koraput and Kalahandi.
The Gangas ruled over Kalahandi for a long period. The stone inscription at Narla reveals that one Madanamahadeva was ruling over Kamalmandala in 1231 A.D. apparently as a feudatory of the Gangas. Tradition preserved by the Durbar of Kalahandi reveals that the Nagas commenced their rule in Kalahandi from Vikram sambat 1062 or A.D. 1005. If the tradition is to be believed it may be said that the Nagas ruled over Kamalmandala as feudatories of the Gangas till 14th century A.D. after which they owed allegiance to the Surjayavamsi Gajapatis.
It is not known when Kamalmandala became known as Kalahandi. The earliest reference to the name Kalahandi is found in the Dadhivaman temple inscription dated in Yugabda 4819, i.e., A.D. 1718. In British records this territory was called Karond. This territory assumed independence after the downfall of the Gajapatis of Orissa in 1568 A.D. According to tradition the Kalahandi kingdom commanded sovereign power over eighteen garhs before it was occupied by the Bhonslas of Nagpur in the middle of the 18th century A.D. In 1803 when the Marhattas were defeated by the British and the coastal regions of Orissa as well as the Patna-Sambalpur group of states came under the British, Kalahandi, very probably, continued under the Marhattas. The Patna-Sambalpur group was subsequently restored to Raghujee Bhonsla II in 1806. The Marhattas of Nagpur became subordinate to British power after the 3rd Anglo-Marhatta War in 1818.But Kalahandi continued to be under Marhatta rule till 1853, when the Nagpur state lapsed to the British Crown as Raghujee III died without an heir. The Chauhans were ruling over Khariar since about the time of Rama Deo, the first Chauhan king of Patna. In 1590 A.D. Gopal Ray, a scion of the Patna family became the king of Khariar and started a line of semi-independent kings in that territory. Khariar came under the Marhattas in 1741 A.D. and the British occupied it in 1818.In 1905 when the District of Sambalpur and some feudatory states including Kalahandi were amalgamated with Orissa Division of Bengal, the Government of the Central Provinces opposed merger of Khariar with Sambalpur and in 1906 Khariar became a part of the Mahasamund tahasil. When the separate province of Orissa was formed in 1936, Khariar was added to Orissa and was made a sub-division (Nuapada sub-division) of Sambalpur District. On the 1st January 1948, Kalahandi alongwith other feudatory states of Orissa except Mayurbhanj, merged with Orissa and on that date the new District of Kalahandi was formed with the ex-states of Kalahandi, Patna and Sonepur. On the 1st November 1949, Patna and Sonepur together constituted a separate District and the Nuapada sub-division of Sambalpur was added to the District of Kalahandi.