Claims for exceptional preservation of biomolecules in the fossil record are contested. Here we demonstrate the role of surface stabilisation in significantly prolonging protein sequence survival to ~3.8 million years. The intracrystalline environment of calcite ostrich (Struthionidae) eggshell encapsulates uterine proteins and molecular dynamics simulations of struthiocalcin-1 & -2, the dominant proteins within the eggshell, reveal that they bind to the mineral surface in distinct domains. By ~3.8 million years the struthiocalcin-1 domain with the lowest calculated binding energy is selectively preserved in eggshell samples from equatorial Africa. Sequence survival is explained by entropy loss of the peptide and water, lowering the effective temperature of the local environment at the peptide mineral interface.