Background: Plant color variation is due not only to the global pigment concentration but also to the proportion of different types of pigment. Variation in the color spectrum may arise from secondary modifications, such as hydroxylation and methylation, affecting the chromatic properties of pigments. In grapes (Vitis vinifera L.), the level of methylation modifies the stability and reactivity of anthocyanin, which directly influence the color of the berry. Anthocyanin methylation, as a complex trait, is controlled by multiple molecular factors likely to involve multiple regulatory steps. Results: In a Syrah x Grenache progeny, two QTLs were detected for variation in level of anthocyanin methylation. The first one, explaining up to 27% of variance, colocalized with a cluster of Myb-type transcription factor genes. The second one, explaining up to 20% of variance, colocalized with a cluster of O-methyltransferase coding genes (AOMT). In a collection of 32 unrelated cultivars, MybA and AOMT expression profiles correlated with the level of methylated anthocyanin. In addition, the newly characterized AOMT2 gene presented two SNPs associated with methylation level. These mutations, probably leading to a structural change of the AOMT2 protein significantly affected the enzyme specific catalytic efficiency for the 3'-O-methylation of delphinidin 3-glucoside. Conclusion: We demonstrated that variation in methylated anthocyanin accumulation is susceptible to involve both transcriptional regulation and structural variation. We report here the identification of novel AOMT variants likely to cause methylated anthocyanin variation. The integration of QTL mapping and molecular approaches enabled a better understanding of how variation in gene expression and catalytic efficiency of the resulting enzyme may influence the grape anthocyanin profile.