MicroRNAs are non-coding small RNAs with regulatory functions, which modulate the growth and development, secondary metabolism and stress response in plants. To explore the miRNAs that are relevant to anthocyanin synthesis in pigmented potatoes, in this study the miRNAs and their target genes were identified using small RNA (sRNA) and degradome sequencing. The physicochemical properties, protein structure, regulatory relationship and expression of miRNAs and target genes in pigmented potato cultivars were analyzed. The results showed that, the miRNA/target gene pair stu-miR156a_R-1/StSPL9, stu-miR828/StMYB3, stu-miR858/StMYB4 and stu-miR5021/StMYB were found with significant negative correlation at different developmental stages in potato tubers. For examples, the miRNA stu-miR828 might negatively regulate the target gene StMYB3, thus inhibiting anthocyanin synthesis, while stu-miR156a_R-1 might promote anthocyanin synthesis via negatively regulating the target gene StSPL9. stu-miR858 was able to negatively regulate the target gene StMYB4, which could promote anthocyanin synthesis in purple potato cultivars and inhibit anthocyanin synthesis in red potato cultivars. stu-miR5021 was a negative regulator for the target gene stMYB, thus suppressing anthocyanin synthesis in purple potato, whereas promoting anthocyanin synthesis in red potato.