The olive fruit fly, specialized to become monophagous during several life stages, remains the most important olive tree pest with high direct production losses, but also affecting the quality, composition, and inherent properties of the olives. Thought to have originated in Africa is nowadays present wherever olive groves are grown. The olive fruit fly evolved to harbor a vertically transmitted and obligate bacterial symbiont -Candidatus Erwinia dacicola- leading thus to a tight evolutionary history between olive tree, fruit fly and obligate, vertical transmitted symbiotic bacterium. Considering this linkage, the genetic diversity (at a 16S fragment) of this obligate symbiont was added in the understanding of the distribution pattern of the holobiont at nine locations throughout four countries in the Mediterranean Basin. This was complemented with mitochondrial (four mtDNA fragments) and nuclear (ten microsatellites) data of the host. We focused on the previously established Iberian cluster for the B. oleae structure and hypothesised that the Tunisian samples would fall into a differentiated cluster. From the host point of view, we were unable to confirm this hypothesis. Looking at the symbiont, however, two new 16S haplotypes were found exclusively in the populations from Tunisia. This finding is discussed in the frame of host-symbiont specificity and transmission mode. To understand olive fruit fly population diversity and dispersion, the dynamics of the symbiont also needs to be taken into consideration, as it enables the fly to, so efficiently and uniquely, exploit the olive fruit resource.