The usefulness of random amplified microsatellite polymorphism markers to study the genetic diversity and relationships among cultivars belonging to Prunus salicina and P. domestica and their wild relatives (P. insititia and P. spinosa) was investigated. A total of 226 of 234 bands were polymorphic (96.58%). The 226 random amplified microsatellite polymorphism markers were screened using 15 random amplified polymorphic DNA and inter-simple sequence repeat primers combinations for 54 Tunisian plum accessions. The percentage of polymorphic bands (96.58%), the resolving power of primers values (135.70), and the polymorphic information content demonstrated the efficiency of the primers used in this study. The genetic distances between accessions ranged from 0.18 to 0.79 with a mean of 0.24, suggesting a high level of genetic diversity at the intra- and interspecific levels. The unweighted pair group with arithmetic mean dendrogram and principal component analysis discriminated cultivars efficiently and illustrated relationships and divergence between spontaneous, locally cultivated, and introduced plum types. These procedures showed continuous variation that occurs independently of the status of the species and geographical origin of the plums. In this study, random amplified microsatellite polymorphism was found to be as a reliable molecular marker for fingerprinting and for examining the diversity study of the plum and its relatives.