Their core territory was known as Kongoda-mandala, and included parts of the present-day Ganjam, Khordha and Puri districts in the Odisha state.

[3] Associating Pulindasena with the ancient Pulinda tribe, historians such as Upinder Singh believe that this myth reflects the tribal origins of the dynasty.

The rulers of this family acknowledged the suzerainty of the Vigraha and Mudgala dynasties, before the Gauda king Shashanka conquered the region.

Historian Snigdha Tripathy theorizes that after conquering present-day Odisha, the Gauda king Shashanka created the Kongoda-mandala province, and appointed Madhavaraja II as his feudatory of the region.

[13] Madhavaraja II may have declared independence taking advantage of Shashanka's conflict with the kings Harsha and Bhaskaravarman.

[15] The inscriptions issued by Madhavaraja II in the later part of reign feature the myth of origin of the Shailodbhava dynasty.

[10] In accordance with the contemporary practices, this mythical origin may have been fabricated by a court poet after the dynasty became independent.

[13] During the reign of Madhavaraja II, around 638 CE, the Chinese pilgrim Xuanzang visited Kongoda (which he calls Kong-u-T'o).

He described it as follows:[16] Within the limits of this country there are several tens of small towns which border on the mountains and are built contiguous to the sea.

The cities themselves are strong and high; the soldiers are brave and daring; they rule by force the neighbouring provinces, so that no one can resist them.

[17] Epigraphic evidence suggests that he ruled for at least 26 years (up to the end of the 7th century), and his reign was peaceful and prosperous.

According to Dharmaraja's inscriptions, he defeated his elder brother Madhava (Madhavaraja III) at Phasika to gain the throne.

Their territory appears to have become part of the Gangas of Shvetaka, who were vassals of the Bhauma-Kara king Unmattakesharin for some time.