The history of Gajapati District still echoes the long gone days of the history of Gajapati rulers in the District. The historical documents of the Gajapati District are accounted from the time when, Krushna Chandra gajapati Narayan Deo ascended the throne of the District. The king of Paralakhemundi Shri Krushna Chandra Gajapati Narayan Deo had the kingship of the majestic Gajapati rulers, who continued to be the supreme authority of Odisha for more than seven centuries. The boundary of Odisha, during that time was extended from the Ganga in the North to Udoyagiri in Nellore District in the South including the entire District of Ganjam. When Kolahomee, one of the sons of Kapilendra Deo, at the later half of the 15th century conquered this part of Odisha, he installed the kingdom and the Raj family of Paralakhemundi.As the past history of Gajapati relates, Paralakhemundi was a zamindary estate at that time, situated at the western nook of the southern most part of the ganjam District. At that time the Maliya tribals dominated the land.
The available historical records depict that it was Gajapati Narayan Deb, who constituted Odisha as a separate province in the Indian Union and finally merged the Paralakhemundi estate to the province of Odisha. The present District of Gajapati came to be existed as a separate functioning unit from 2nd October 1992.
There are many historical monuments and places that reveals the historical touch of the District. Tomb of the Royal family, B.N Palace, Serango, Mahendragiri, Jeerango etc are some monuments and places in the District that are famous for its historical importance.