Successful prevention and mitigation of biological invasions requires retracing the initial steps of introduction, as well as understanding key elements enhancing the adaptability of invasive species. We studied the genetic diversity of the green alga Caulerpa taxifolia and its associated bacterial communities in several areas around the world. The striking congruence of alpha and beta diversity of the algal genome and endophytic communities reveals a tight association, supporting the holobiont concept as best describing the unit of spreading and invasion. Both genomic compartments support the hypotheses of a unique accidental introduction in the Mediterranean and of multiple invasion events in southern Australia. In addition to helping with tracing the origin of invasion, bacterial communities exhibit metabolic functions that can potentially enhance adaptability and competitiveness of the consortium they form with their host. We thus hypothesize that low genetic diversities of both host and symbiont communities may contribute to the recent regression in the Mediterranean, in contrast with the persistence of highly diverse assemblages in southern Australia. This study supports the importance of scaling up from the host to the holobiont for a comprehensive understanding of invasions.