A total of 91 wild olive accessions and 31 olive cultivars growing in the Extremadura region of central-western Spain were analyzed using morphological traits and RAPD markers. We focused on three main and 16 minor Spanish olive cultivars that are recognized as native or local to the Extremadura region. The five arbitrary 10-mer primers tested on the olive cultivars gave 67 polymorphic bands, representing 91% of the total amplification products. The number of bands per primer ranged from 9 to 18, whereas the number of polymorphic bands ranged from 8 to 17. All the cultivars could be identified by a combination of three primers (OPF-6, OPA-8, and OPK-16); four cultivar-specific markers were detected. The minor local “Jariego” and “Tempranillo” cultivars showed the most distal similarities. The resulting dendrogram, using the unweighted pair-group method with arithmetic mean clustering algorithm, depicted the pattern of relationships between the local Extremadura cultivars and the cultivars from geographically connected regions. This analysis showed a correlation between most of the minor local cultivars and the geographical origin; there was no apparent clustering according to morphological traits or fruit use of olive cultivars when these parameters were used as analysis criteria.