The consumption of human flesh, popularly defined as cannibalism, has arguably occurred throughout much of human history. In New Guinea, it has been associated ethnographically with warfare, mortuary rites and nutrition. However, it often evades detection in the archaeological record because of difficulties in distinguishing it from other social practices. Here we disentangle colonial myths associated with the consumption of human flesh and report disarticulated, burnt and cut human skeletal remains from two coastal sites spanning the past 540 years in the Massim island region of southeast Papua New Guinea. These sites, Wule and Morpa, both occur on Rossel Island. The skeletal evidence is contemporary with the construction of large stone platforms where human victims were often killed and consumed, and inland villages which were established in response to a well-attested period of conflict on Rossel and throughout the region. Within an ethnoarchaeological framework, we argue that cannibalism became increasingly prevalent in association with feasting as a means of maintaining social relationships and personal power. The findings are placed first within an island, then a regional model of emerging pressures on existing socio-political systems.