We used high-sensitivity, high-resolution tandem mass spectrometry to shotgun sequence ancient protein remains extracted from a 43 000 year old woolly mammoth (Mammuthus primigenius) bone preserved in the Siberian permafrost. For the first time, 126 unique protein accessions, mostly low-abundance extracellular matrix and plasma proteins, were confidently identified by solid molecular evidence. Among the best characterized was the carrier protein serum albumin, presenting two single amino acid substitutions compared to extant African (Loxodonta africana) and Indian (Elephas maximus) elephants. Strong evidence was observed of amino acid modifications due to post-mortem hydrolytic and oxidative damage. A consistent subset of this permafrost bone proteome was also identified in more recent Columbian mammoth (Mammuthus columbi) samples from temperate latitudes, extending the potential of the approach described beyond subpolar environments. Mass spectrometry-based ancient protein sequencing offers new perspectives for future molecular phylogenetic inference and physiological studies on samples not amenable to ancient DNA investigation. This approach therefore represents a further step into the ongoing integration of different high-throughput technologies for identification of ancient biomolecules, unleashing the field of paleoproteomics.