Parlakhemundi estate was a Zamindari of Odisha in the British Raj period .Before odisha province formation it was under Madras Presidency.The state was ruled as an independent kingdom till 1769.The royal family belong to the Krishnatreya gotra Odia Kshatriya and traced their lineage to Eastern Ganga Dynasty.It was a zamindari estate lying in the southwestern portion of Ganjam district, covering an area of 615 square miles. It was bounded in the south by the district of Vizagpatnam and on the west by the Jeypore Estate and the tribal agencies of the Eastern Ghats.

The Eastern Ganga dynasty were a large medieval era Indian royal Hindu dynasty that reigned from Kalinga from as early as the 5th century to the mid 20th century. Eastern Gangas ruled much of the modern region of Odisha in three different phases by the passage of time, known as Early Eastern Gangas (493–1077), Imperial Eastern Gangas (1077–1436) and Khemundi Gangas (1436–1947). They are known as "Eastern Gangas" to distinguish them from the Western Gangas who ruled over Karnataka. The territory ruled by the dynasty consisted of the whole of the modern-day Indian state of Odisha, as well as major parts of north Andhra Pradesh, parts of Chhattisgarh and some southern districts of West Bengal. Odia language got official status in their regime following the evolution of the language from Odra Prakrit. The early rulers of the dynasty ruled from Dantapuram; the capital was later moved to Kalinganagara, and ultimately to Kataka and then to Paralakhemundi.