The aim of the present study was to develop a reliable reference database to discriminate between the major Greek olive (Olea europaea L.) cultivars and reveal their genetic relationships, since Greece is considered a secondary center of diversity. In order to establish genetic relationships among the 26 Greek and eight international cultivars, four amplified fragment length polymorphism (AFLP) primer pairs, 12 randomly amplified polymorphic DNA (RAPD) primers, along with measurements from 10 morphological traits, were used. A total of 576 AFLP and 113 RAPD markers were produced. Genetic similarities, estimated using the Jaccard algorithim, ranged from 0.45 to 0.83 for the AFLP data and 0.27 to 0.87 for the RAPD data. The cophenetic correlation coefficients between the genetic similarities and the unweighted pair group method of arithmetic averages (UPGMA) phenograms were 0.77 for the AFLPs, 0.81 for the RAPDs, and 0.69 for the morphological traits. However, limited clustering similarities among the phenograms derived from the three methods were observed. This was also reflected by the low correlation between the three genetic similarity matrices produced (AFLP and RAPD, r = 0.39; AFLP and morphological traits, r = 0.11; RAPD and morphological traits, r = 0.02). According to the molecular results, olive cultivars are clustered according to fruit size but not according to geographical origin. Three of the cultivars tested, `Vasilicada,' `Throumbolia', and `Lianolia Kerkiras', were found to branch distantly to the others, according to the AFLP results, and can be considered as ancient Greek cultivars.