BACKGROUND AND AIMS: The genus Olea (Oleaceae) includes approx. 40 taxa of evergreen shrubs and trees classified in three subgenera, Olea, Paniculatae and Tetrapilus, the first of which has two sections (Olea and Ligustroides). Olive trees (the O. europaea complex) have been the subject of intensive research, whereas little is known about the phylogenetic relationships among the other species. To clarify the biogeographical history of this group, a molecular analysis of Olea and related genera of Oleaceae is thus necessary. METHODS: A phylogeny was built of Olea and related genera based on sequences of the nuclear ribosomal internal transcribed spacer-1 and four plastid regions. Lineage divergence and the evolution of abaxial peltate scales, the latter character linked to drought adaptation, were dated using a Bayesian method. KEY RESULTS: Olea is polyphyletic, with O. ambrensis and subgenus Tetrapilus not sharing a most recent common ancestor with the main Olea clade. Partial incongruence between nuclear and plastid phylogenetic reconstructions suggests a reticulation process in the evolution of subgenus Olea. Estimates of divergence times for major groups of Olea during the Tertiary were obtained. CONCLUSIONS: This study indicates the necessity of revising current taxonomic boundaries in Olea. The results also suggest that main lines of evolution were promoted by major Tertiary climatic shifts: (1) the split between subgenera Olea and Paniculatae appears to have taken place at the Miocene-Oligocene boundary; (2) the separation of sections Ligustroides and Olea may have occurred during the Early Miocene following the Mi-1 glaciation; and (3) the diversification within these sections (and the origin of dense abaxial indumentum in section Olea) was concomitant with the aridification of Africa in the Late Miocene.