The olive tree (Olea europaea) has successfully invaded several regions in Australia and Pacific islands. Two olive subspecies (subspp. europaea and cuspidata) were first introduced in these areas during the nineteenth century. In the present study, we determine the origin of invasive olives and investigate the importance of historical effects on the genetic diversity of populations. Four invasive populations from Australia and Hawaii were characterized using eight nuclear DNA microsatellites, plastid DNA markers as well as ITS-1 sequences. Based on these data, their genetic similarity with native populations was investigated, and it was determined that East Australian and Hawaiian populations (subsp. cuspidata) have originated from southern Africa while South Australian populations (subsp. europaea) have mostly derived from western or central Mediterranean cultivars. Invasive populations of subsp. cuspidata showed significant loss of genetic diversity in comparison to a putative source population, and a recent bottleneck was evidenced in Hawaii. Conversely, invasive populations of subsp. europaea did not display significant loss of genetic diversity in comparison to a native Mediterranean population. Different histories of invasion were inferred for these two taxa with multiple cultivars introduced restoring gene diversity for europaea and a single successful founder event and sequential introductions to East Australia and then Hawaii for cuspidata. Furthermore, one hybrid (cuspidata x europaea) was identified in East Australia. The importance of hybridizations in the future evolution of the olive invasiveness remains to be investigated.