Ancient DNA (aDNA) is the most informative biomolecule extracted from skeletal remains at archaeological sites, but its survival is unpredictable and its extraction and analysis is time consuming, expensive and often fails. Several proposed methods for better understanding aDNA survival are based upon the characterisation of some aspect of protein survival, but these are typically non-specific; proteomic analyses may offer an attractive method for understanding preservation processes. In this study, in-depth proteomic (LC-Orbitrap-MS/MS) analyses were carried out on 69 archaeological bovine bone and dentine samples from multiple European archaeological sites and compared with mitochondrial aDNA and amino acid racemisation (AAR) data. Comparisons of these data, including estimations of the relative abundances for seven selected non-collagenous proteins, indicate that the survival of aDNA in bone or dentine may correlate with the survival of some proteins, and that proteome complexity is a more useful predictor of aDNA survival than protein abundance or AAR. The lack of a strong correlation between the recovery of aDNA and the proteome abundance may indicate that the survival of aDNA is more closely linked to its ability to associate with bone hydroxyapatite crystals rather than to associate with proteins.Ancient biomolecule survival remains poorly understood, even with great advancements in 'omics' technologies, both in genomics and proteomics. This study investigates the survival of ancient DNA in relation to that of proteins, taking into account proteome complexity and the relative protein abundances to improve our understanding of survival mechanisms. The results show that although protein abundance is not necessarily directly related to aDNA survival, proteome complexity appears to be.