We have used a paleogenetics approach to investigate the genetic landscape of coat color variation in ancient Eurasian dog and wolf populations. We amplified DNA fragments of two genes controlling coat color, Mc1r (Melanocortin 1 Receptor) and CBD103 (canine-β-defensin), in respectively 15 and 19 ancient canids (dogs and wolf morphotypes) from 14 different archeological sites, throughout Asia and Europe spanning from ca. 12 000 B.P. (end of Upper Palaeolithic) to ca. 4000 B.P. (Bronze Age). We provide evidence of a new variant (R301C) of the Melanocortin 1 receptor (Mc1r) and highlight the presence of the beta-defensin melanistic mutation (CDB103-K locus) on ancient DNA from dog-and wolf-morphotype specimens. We show that the dominant K(B) allele (CBD103), which causes melanism, and R301C (Mc1r), the variant that may cause light hair color, are present as early as the beginning of the Holocene, over 10 000 years ago. These results underline the genetic diversity of prehistoric dogs. This diversity may have partly stemmed not only from the wolf gene pool captured by domestication but also from mutations very likely linked to the relaxation of natural selection pressure occurring in-line with this process.