Phylogenetic relationships among nine species in the genus Pistacia were studied by randomly amplified polymorphic DNA (RAPD) analysis. The following species were included: P. atlantica, P. terebinthus, A eurycarpa, P. vera, A integerrima, P. mexicana, P. palaestina, P. lentiscus, and P. khinjuk. Genomic DNA was extracted from leaf tissue and RAPD analysis was performed using 20 primers. A total of 242 fragments were generated and 228 bands were polymorphic at the inter-specific level. Subjecting these data to phylogenetic analysis yielded a shortest cladogram that is 338 steps long, featuring two main groups. P. vera, P. khinjuk, P. eurycarpa, P. atlantica, and P. integerrima were included in one group, while P. terebinthus, P. palaestina, P. mexicana, and P. lentiscus formed the second group. The first group included species with single-trunked and big trees, whereas the species included in the second group mostly grow as shrubs or small trees. The cladogram showed that the closest pairs of species were P. terebinthus and P. palaestina, P. eurycarpa and A atlantica, P. vera and P. khinjuk, and P. mexicana and P. lentiscus. We suggest that A palaestina is in fact a variety of P. terebinthus in view of the small genetic distance between them. This study also showed that P. eurycarpa (syn. P. atlantica var. kurdica) is a distinct species from P. atlantica, rather than a variety within the same species.