Reduction in population size and local extinctions have been reported for the yellow-bellied toad, Bombina variegata, but the genetic impact of this is not yet known. In this study, we genotyped 200 individuals, using mtDNA cytochrome b and 11 nuclear microsatellites. We investigated fine-scale population structure and tested for genetic signatures of historical and recent population decline, using several statistical approaches, including likelihood methods and approximate Bayesian computation. Five major genetically divergent groups were found, largely corresponding to geography but with a clear exception of high genetic isolation in a highly touristic area. The effective sizes in the last few generations, as estimated from the random association among markers, never exceeded a few dozen of individuals. Our most important result is that several analyses converge in suggesting that genetic variation was shaped in all groups by a 7- to 45-fold demographic decline, which occurred between a few hundred and a few 1000 years ago. Remarkably, only weak evidence supports recent genetic impact related to human activities. We believe that the alpine B. variegata populations should be monitored and protected to stop their recent decline and to prevent local extinctions, with highest priority given to genetically isolated populations. Nonetheless, current genetic variation pattern, being mostly shaped in earlier times, suggests that complete recovery can be achieved. In general, our study is an example of how the potential for recovery should be inferred even under the co-occurrence of population decline, low genetic variation, and genetic bottleneck signals.