In a significant section of available scholarship on pre-Islamic Bengal, a dominant tendency has been to generalize the patterns of historical trajectories of the great river valleys. This has resulted in many discrepancies, particularly in the context of the plateau-like portions of southwestern Bengal, where, unlike other parts of Bengal, Jainism came to have an entrenched presence during the early medieval period (c.600–1200 ce). Through an analysis of the published archaeological data, this paper attempts to study the social history of Jaina and Brahmanical temples and their linkages with the political processes in a forested frontier of early medieval southwestern Bengal: Purulia. This district, marked with an absence of early historical farming cultures, was an extension of the Chhotanagpur plateau of Jharkhand. During the early medieval period, this district witnessed three coeval and interrelated processes: large-scale construction of Jaina and Brahmanical (primarily Saiva) temples, emergence of a local state, and widespread construction of hero stones. The political elites of the major political centre of the local state that emerged in this area seem to have derived their legitimacy by patronizing Saiva temples, but Jaina temples seem to have provided the primary avenue for the legitimation of local heroes after their death, who were immortalized in hero stones.