Recent DNA studies have shown that selected populations in Southeast Asia, and Oceania in particular, have inherited genetic material from Denisovans, with the highest percentage found in New Guinea and Aboriginal Australians. Multiple divergent ancestries are seen in New Guinea with two unique Denisovan lineages; the latest (D1) occurring as late as ~30-15 k years ago. While hugely relevant for understanding hominin dispersals, admixture and adaptation, the Pleistocene and early Holocene archaeological and, especially, palaeoanthropological records of the New Guinea region are sparse and poorly understood. The rarity of hominin fossils from this region is a significant limitation in testing current hypotheses on Denisovan presence in Sahul during the Late Pleistocene. Through the extensive application of Zooarchaeology by Mass Spectrometry (ZooMS) analyses of unidentified bone fragments, new hominin fossils can be identified if ancient collagen is preserved. This paper will present ZooMS results stemming from the FINDER Project (ERC-715069) with 535 samples from 10 New Guinea sites; an attempt that has succeeded in expanding the record of hominin fossils in this region. We also observed a much-improved preservation of archaeological collagen in the New Guinea Highlands compared to the coastal regions. We will discuss how these analyses provides the perfect opportunity to test organic material preservation in archaeological bones to find candidate samples not only suitable for palaeoproteomic analyses, but also for isotopic, dating and genetic applications. Finally, we will consider how the widespread screening of old collections and material excavated, even several decades ago, has the potential to provide significant new information for the prehistoric record of SE Asia and Oceania.