High-throughput proteomic analysis of archaeological skeletal remains provides information about past fauna community compositions and species dispersals in time and space. Archaeological skeletal remains are a finite resource, however, and therefore it becomes relevant to optimize methods of skeletal proteome extraction. Ancient proteins in bone specimens can be highly degraded and consequently, extraction methods for well-preserved or modern bone might be unsuitable for the processing of highly degraded skeletal proteomes. In this study, we compared six proteomic extraction methods on Late Pleistocene remains with variable levels of proteome preservation. We tested the accuracy of species identification, protein sequence coverage, deamidation, and the number of post-translational modifications per method. We find striking differences in obtained proteome complexity and sequence coverage, highlighting that simple acid-insoluble proteome extraction methods perform better in highly degraded contexts. For well-preserved specimens, the approach using EDTA demineralization and protease-mix proteolysis yielded a higher number of identified peptides. The protocols presented here allowed protein extraction from ancient bone with a minimum number of working steps and equipment and yielded protein extracts within three working days. We expect further development along this route to benefit large-scale screening applications of relevance to archaeological and human evolution research.