Palaeoproteomics of skeletal tissues has the potential to provide new insights into the evolutionary relationships between globally distributed hominin fossils across the Pleistocene. The use of alternative or additional proteases has the potential to increase both proteome size and protein. However, the potential of alternative proteases beside trypsin remains unexplored systematically in palaeoproteomic studies. Here, we present a comparison of the bone proteome size and protein sequence recovery of six different proteases from four Pleistocene bone specimens. We observe that the majority of the preserved bone proteome is inaccessible to trypsin. We also note that for proteins recovered consistently across several proteases, protein sequence coverage can be increased significantly by combining peptide identifications from two or more proteases. Our results thereby demonstrate that the proteolysis of Pleistocene proteomes by several proteases has clear advantages when addressing evolutionary questions in palaeoproteomics.