Anthocyanins are a chemically diverse class of secondary metabolites that color most flowers and fruits. They consist of three aromatic rings that can be substituted with hydroxyl, sugar, acyl, and methyl groups in a variety of patterns depending on the plant species. To understand how such chemical diversity evolved, we isolated and characterized METHYLATION AT THREE2 (MT2) and the two METHYLATION AT FIVE (MF) loci from Petunia spp., which direct anthocyanin methylation in petals. The proteins encoded by MT2 and the duplicated MF1 and MF2 genes and a putative grape (Vitis vinifera) homolog Anthocyanin O-Methyltransferase1 (VvAOMT1) are highly similar to and apparently evolved from caffeoyl-Coenzyme A O-methyltransferases by relatively small alterations in the active site. Transgenic experiments showed that the Petunia spp. and grape enzymes have remarkably different substrate specificities, which explains part of the structural anthocyanin diversity in both species. Most strikingly, VvAOMT1 expression resulted in the accumulation of novel anthocyanins that are normally not found in Petunia spp., revealing how alterations in the last reaction can reshuffle the pathway and affect (normally) preceding decoration steps in an unanticipated way. Our data show how variations in gene expression patterns, loss-of-function mutations, and alterations in substrate specificities all contributed to the anthocyanins' structural diversity. © 2014 American Society of Plant Biologists. All rights reserved.