Among the many fish species commercially exploited since prehistoric times, Atlantic bluefin tuna (Thunnus thynnus) is one of the most economically significant, having left an indelible imprint on several civilizations including the Phoenicians, Greeks, and Romans. Here, we describe our efforts to identify tuna specimens among the remains of 345 fish vertebrae and bones in several large collections from the Atlantic Ocean, Mediterranean Sea, and Black Sea, dating from the Late Iron Age (2nd century BCE) to the early 20th century (1911-1927). Unfortunately, ancient fish specimens are often mislabelled, which can cause a great deal of confusion among zoologists. Protocols were developed and optimized to overcome the unique challenges related to the compromised integrity of genetic material preserved in ancient bones. Three DNA isolation protocols were compared to maximize yields, and as reported for other faunal remains, a silica spin column-based method was proven most effective. Endogenous DNA was successfully extracted from the majority of bones and amplified using polymerase chain reactions (PCRs) and an assortment of four primer pairs targeting nuclear (internal transcribed spacer) and mitochondrial sequences (cytochrome oxidase subunit 1 and control region). Protocols targeting mitochondrial markers were more successful than those focused on nuclear targets. Due to the restricted length of the extracted DNA molecules, character-based keys containing diagnostic nucleotide substitutions were defined and used to identify 231 samples to genera, of which 171 were identified to species level. The success rate of assignment of specimens to species level varied between location and collection, reflecting variation in DNA preservation between different sites and environments. The methods detailed herein can be used to identify other ancient fish specimens and provide information about historical human diets, trade, species distribution, and biodiversity. The same tools can be applied to the analysis of processed food items with highly damaged DNA.