New Guinea was host to some of the most complex maritime interaction networks in the tropics. We take a multi-proxy approach to investigate the foodways at the heart of the extensive Madang exchange network, in the last millennium before the present: 1) invertebrate zooarchaeological analysis identifies the dependence on shellfish collecting from the coral reef and sandy floor littoral zone; 2) examination of vertebrate remains demonstrates the rearing and consumption of key domesticated animals (pigs and perhaps dogs), alongside reef fish, birds, and possibly snakes; 3) human dental calculus analysis distinguishes that marine plants, palm, betelnut, and probably banana were consumed; 4) pottery residue analysis suggests that a variety of starchy crops were being cooked in locally made ceramics. We use this information to develop interpretations about the nature of land-use, mobility, and exchange along New Guinea’s coastal fringe, as well as how foodways have transformed throughout the Late Holocene.