The realization that ancient biomolecules are preserved in "fossil" samples has revolutionized archaeological science. Protein sequences survive longer than DNA, but their phylogenetic resolution is inferior; therefore, careful assessment of the research questions is required. Here, we show the potential of ancient proteins preserved in Pleistocene eggshell in addressing a longstanding controversy in human and animal evolution: the identity of the extinct bird that laid large eggs which were exploited by Australia's indigenous people. The eggs had been originally attributed to the iconic extinct flightless bird Genyornis newtoni (†Dromornithidae, Galloanseres) and were subsequently dated to before 50 ± 5 ka by Miller et al. [Nat. Commun. 7, 10496 (2016)]. This was taken to represent the likely extinction date for this endemic megafaunal species and thus implied a role of humans in its demise. A contrasting hypothesis, according to which the eggs were laid by a large mound-builder megapode (Megapodiidae, Galliformes), would therefore acquit humans of their responsibility in the extinction of Genyornis. Ancient protein sequences were reconstructed and used to assess the evolutionary proximity of the undetermined eggshell to extant birds, rejecting the megapode hypothesis. Authentic ancient DNA could not be confirmed from these highly degraded samples, but morphometric data also support the attribution of the eggshell to Genyornis. When used in triangulation to address well-defined hypotheses, paleoproteomics is a powerful tool for reconstructing the evolutionary history in ancient samples. In addition to the clarification of phylogenetic placement, these data provide a more nuanced understanding of the modes of interactions between humans and their environment.