Anthocyanins are important pigments and are responsible for red coloration in plums. However, little is known about the molecular mechanisms underlying anthocyanin accumulation in plum fruits. In this study, the RNA-seq technique was used to analyze the transcriptomic changes during fruit ripening in the red-fleshed plum (Prunus salicina Lindl.) cultivar ‘Furongli’. Over 161 million high-quality reads were assembled into 52,093 unigenes and 49.4% of these were annotated using public databases. Of these, 25,681 unigenes had significant hits to the sequences in the NCBI Nr database, 17,203 unigenes showed significant similarity to known proteins in the Swiss-Prot database and 5816 and 8585 unigenes had significant similarity to existing sequences in the Kyoto Encyclopedia of Genes and Genomes and the Cluster of Orthologous Groups databases, respectively. A total of 3548 unigenes were differentially expressed during fruit ripening and 119 of these were annotated as involved in “biosynthesis of other secondary metabolites.” Biological pathway analysis and gene ontology term enrichment analysis revealed that 13 differentially expressed genes are involved in anthocyanin biosynthesis. Furthermore, transcription factors such as MYB and bHLH, which may control anthocyanin biosynthesis, were identified through coexpression analysis of transcription factors, and structural genes. Real-time qPCR analysis of candidate genes showed good correlation with the transcriptome data. These results contribute to our understanding of the molecular mechanisms underlying anthocyanin biosynthesis in plum flesh. The transcriptomic data generated in this study provide a basis for further studies of fruit ripening in plum.