Abstract Background Ecosystem engineers facilitate habitat formation and enhance biodiversity, but when they become invasive, they present a critical threat to native communities because they can drastically alter the receiving habitat. Management of such species thus needs to be a priority, but the poorly resolved taxonomy of many ecosystem engineers represents a major obstacle to correctly identifying them as being either native or introduced. We address this dilemma by studying the sea squirt Pyura stolonifera, an important ecosystem engineer that dominates coastal communities particularly in the southern hemisphere. Using DNA sequence data from four independently evolving loci, we aimed to determine levels of cryptic diversity, the invasive or native status of each regional population, and the most appropriate sampling design for identifying the geographic ranges of each evolutionary unit. Results Extensive sampling in Africa, Australasia and South America revealed the existence of "nested" levels of cryptic diversity, in which at least five distinct species can be further subdivided into smaller-scale genetic lineages. The ranges of several evolutionary units are limited by well-documented biogeographic disjunctions. Evidence for both cryptic native diversity and the existence of invasive populations allows us to considerably refine our view of the native versus introduced status of the evolutionary units within Pyura stolonifera in the different coastal communities they dominate. Conclusions This study illustrates the degree of taxonomic complexity that can exist within widespread species for which there is little taxonomic expertise, and it highlights the challenges involved in distinguishing between indigenous and introduced populations. The fact that multiple genetic lineages can be native to a single geographic region indicates that it is imperative to obtain samples from as many different habitat types and biotic zones as possible when attempting to identify the source region of a putative invader. "Nested" cryptic diversity, and the difficulties in correctly identifying invasive species that arise from it, represent a major challenge for managing biodiversity.