Recent improvements in the analysis of ancient biomolecules from human remains and associated dental calculus have provided new insights into the prehistoric diet and genetic diversity of our species. Here we present a multi-omics study, integrating metagenomic and proteomic analyses of dental calculus, and human ancient DNA analysis of the petrous bones of two post-Last Glacial Maximum (LGM) individuals from San Teodoro cave (Italy), to reconstruct their lifestyle and the post-LGM resettlement of Europe. Our analyses show genetic homogeneity in Sicily during the Palaeolithic, representing a hitherto unknown Italian genetic lineage within the previously identified Villabruna cluster. We argue that this lineage took refuge in Italy during the LGM, followed by a subsequent spread to central-western Europe. Analysis of dental calculus showed a diet rich in animal proteins which is also reflected on the oral microbiome composition. Our results demonstrate the power of this approach in the study of prehistoric humans and will enable future research to reach a more holistic understanding of the population dynamics and ecology.