Genetic structure and evolutionary patterns of the wild olive tree (Olea europaea L.) were investigated with AFLP fingerprinting data at three geographic levels: (a) phylogenetic relationships of the six currently recognized subspecies in Eurasia and Africa; (b) lineage identification in subsp. europaea of the Mediterranean basin; and (c) phylogeography in the western Mediterranean. Two statistical approaches (Bayesian inference and analysis of molecular variance) were used to analyse the AFLP fingerprints. To determine the congruency and transferability of results across studies previous RAPD and ISSR data were analysed in a similar manner. Comparisons proved that qualitative results were mostly congruent but quantitative values differed, depending on the method of analysis. Neighbour-Joining analysis of AFLP phenotypes supported current classification of subspecies. At a Mediterranean scale no clear cut phylogeographic pattern was recovered, likely due to extensive gene flow between populations of subsp. europaea. Gene flow estimates calculated with conventional F-statistics showed that reproductive barriers separated neither populations nor lineages of O. europaea. Genetic divergence between eastern and western parts of the Mediterranean basin was observed only when geographical and population information were incorporated into the analyses through hierarchical analysis of molecular variance (AMOVA). Within the western Mediterranean, the highest genetic diversity was found in two regions: on both sides of the Strait of Gibraltar and in the Balearic archipelago. Additionally, long-lasting isolation of the northern-most populations of the Iberian Peninsula appeared to be responsible for a significant divergence.