Over the past two decades, proteomic analysis has greatly developed in application to the field of biomolecular archaeology, coinciding with advancements in LC–MS/MS instrumentation sensitivity and improvements in sample preparation methods. Recently, human dental calculus has received much attention for its well-preserved proteomes locked in mineralized dental plaque which stores information on human diets and the oral microbiome otherwise invisible to other biomolecular approaches. Maximizing proteome recovery in ancient dental calculus, available only in minute quantities and irreplaceable after destructive analysis, is of paramount importance. Here, we compare the more traditional ultrafiltration-based and acetone precipitation approaches with the newer paramagnetic bead approach in order to test the influence of demineralization acid on recovered proteome complexity obtained from specimens as well as the sequence coverages matched for significant proteins. We found that a protocol utilizing EDTA combined with paramagnetic beads increased proteome complexity, in some cases doubling the number of unique peptides and number of proteins matched, compared to protocols involving the use of HCl and either acetone precipitation or ultrafiltration. Although the increase in the number of proteins was almost exclusively of bacterial origin, a development that has implications for the study of diseases within these ancient populations, an increase in the peptide number for the dairy proteins β-lactoglobulin and casein was also observed reflecting an increase in sequence coverage for these dietary proteins of interest. We also consider structural explanations for the discrepancies observed between these two key dietary proteins preserved in archaeological dental calculus.