Gray wolves (Canis lupus) in the Iberian Peninsula declined substantially in both range and population size in the last few centuries due to human persecution and habitat fragmentation. However, unlike many other western European populations, gray wolves never went extinct in Iberia. Since the minimum number was recorded around 1970, their numbers have significantly increased and then stabilized in recent decades. We analyzed mitochondrial genomes from 54 historical specimens of Iberian wolves from across their historical range using ancient DNA methods. We compared historical and current mitochondrial diversity in Iberian wolves at the 5′ end of the control region (n = 17 and 27) and the whole mitochondrial genome excluding the control region (n = 19 and 29). Despite an increase in population size since the 1970s, genetic diversity declined. We identified 10 whole mitochondrial DNA haplotypes in 19 historical specimens, whereas only six of them were observed in 29 modern Iberian wolves. Moreover, a haplotype that was restricted to the southern part of the distribution has gone extinct. Our results illustrate a lag between demographic and genetic diversity changes, and show that after severe population declines, genetic diversity can continue to be lost in stable or even expanding populations. This suggests that such populations may be of conservation concern even after their demographic trajectory has been reversed.