Four hundred and four individuals belonging to the species Olea europaea were characterised using mitochondrial DNA (mtDNA) RFLPs. Twelve mitotypes were distinguished. The combination of mtDNA information with cpDNA polymorphism (characterised in a previous study) led us to recognise 20 cytoplasmic lineages of which seven were found in the Mediterranean area (oleasters, cultivars and O. e. subsp. maroccana). In the olive complex, strong cytoplasm genetic differentiation was revealed ( F(st) = 0.73). Very strong linkage disequilibrium between cpDNA and mtDNA polymorphisms was observed, particularly in the Mediterranean subspecies europaea. This high congruence between genetic structure based on cpDNA or mtDNA sustains a low level of recurrent mutation in both organelle DNAs and, thus, the polymorphisms used in this study were pertinent to reconstruct olive phylogeography. In the Mediterranean area, genetic drift due to population regression during Quaternary glaciations, and founder effects associated with the postglacial seed dissemination, have probably contributed to the existence of a high genetic linkage disequilibrium between cpDNA and mtDNA polymorphisms. Thus, four Mediterranean cytoplasmic lineages, clearly distinguished both by cpDNA and mtDNA polymorphisms, most likely reflect four distinct relic populations during Quaternary glaciations. Finally, O. e. subsp. maroccana from South Morocco, which also displayed specific cytoplasmic lineages, should be considered as another relic Mediterranean population.