The history of Gajapati still echoes the long gone days of the history of Gajapati rulers in the district. Since the tract of the Gajapati was the part of the old Gondowana land, the district existed even in the prehistoric ages. But the historical documents of Gajapati are accounted from the time when, Krushna Chandra Gajapati Narayan Deo ascended the throne of the Gajapati district. Due to the non-existence of any archeological evidences, the authentic historical documents of the prehistoric ages are unavailable

The king Krushna Chandra Gajapati Narayan Deo of Paralakhemundi had the kinship of the majestic Gajapati rulers, who continued to be the supreme authority of Orissa for more tan seven centuries. The boundary of Orissa, 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 Orissa, 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 southernmost part of the Ganjam district. At that time the Maliya tribals dominated the land. The entire tract of Paralakhemundi was bordered by Vizagpatnam in the north and Eastern Ghats in the South.

The history of Gajapati is not apparent enough to indicate the origin of the district or the contemporary socio-economic life. The available historical records depict that the Gajapati district has been named according to the Maharaja Sri Krushna Chandra Gajapati Narayan Deb, the ex raja Sahib of Paralakhemundi (he was even the first Prime Minister of Orissa, after the independence). It was Gajapati Narayan Deb, who constituted Orissa as a separate province in the Indian Union and finally merged the Paralakhemundi estate to the province of Orissa. The present district of Gajapati came to be existed as a separate functioning unit from 2nd October 1992.