One hundred and seventy-three years ago, the last two Great Auks, Pinguinus impennis, ever reliably seen were killed. Their internal organs can be found in the collections of the Natural History Museum of Denmark, but the location of their skins has remained a mystery. In 1999, Great Auk expert Errol Fuller proposed a list of five potential candidate skins in museums around the world. Here we take a palaeogenomic approach to test which—if any—of Fuller’s candidate skins likely belong to either of the two birds. Using mitochondrial genomes from the five candidate birds (housed in museums in Bremen, Brussels, Kiel, Los Angeles, and Oldenburg) and the organs of the last two known individuals, we partially solve the mystery that has been on Great Auk scholars’ minds for generations and make new suggestions as to the whereabouts of the still-missing skin from these two birds.