Anthocyanin content of potato tubers is a trait that is attracting increasing attention as the potential nutritional benefits of this class of compound become apparent. However, our understanding of potato tuber anthocyanin accumulation is not complete. The aim of this study was to use a potato microarray to investigate gene expression patterns associated with the accumulation of purple tuber anthocyanins. The advanced potato selections, CO97216-3P/PW and CO97227-2P/PW, developed by conventional breeding procedures, produced tubers with incomplete expression of tuber flesh pigmentation. This feature permits sampling pigmented and non-pigmented tissues from the same tubers, in essence, isolating the factors responsible for pigmentation from confounding genetic, environmental, and developmental effects. An examination of the transcriptome, coupled with metabolite data from purple pigmented sectors and from non-pigmented sectors of the same tuber, was undertaken to identify these genes whose expression correlated with elevated or altered polyphenol composition. Combined with a similar study using eight other conventional cultivars and advanced selections with different pigmentation, it was possible to produce a refined list of only 27 genes that were consistently differentially expressed in purple tuber tissues compared with white. Within this list are several new candidate genes that are likely to impact on tuber anthocyanin accumulation, including a gene encoding a novel single domain MYB transcription factor.