In the past few decades, in the marine realm in particular, the use of molecular tools has led to the discovery of hidden taxonomic diversity, revealing complexes of sister species. A good example is the red algal genus Asparagopsis. The two species (A. armata and A. taxiformis) recognized in this genus have been introduced in many places around the world. Within the nominal species A. taxiformis, previous molecular analyses have uncovered several lineages, suggesting the existence of sister species or subspecies. Although the genus has been well studied in some regions (e.g., the Mediterranean Sea and Hawaii), it remains poorly investigated in others (e.g., South Pacific). Our study mainly focused on these latter areas to clarify lineages and better determine lineage status (i.e., native vs. introduced). A total of 188 specimens were collected from 61 sites, 58 of which had never been sampled before. We sequenced the DNA from samples for three markers and obtained 112 sequences for the chloroplastic RuBisCo spacer, 118 sequences for the nuclear LSU rRNA gene, and 174 for the mitochondrial spacer cox2-3. Phylogenetic analyses using all three markers suggested the existence of two cryptic sister species with the discovery of a new clade within A. armata. This clade was found only in Western Australia, Tasmania and New Zealand, and is thus restricted to a subregional biogeographic unit. We also discovered a new, fifth lineage for A. taxiformis restricted to the South Pacific and Western Australia. Except for this newly described lineage, all other lineages showed a global distribution influenced by introduction events. These results illustrate the difficulty in accurately defining cosmopolitan species. Our findings also highlight the need for targeted (i.e., in poorly studied areas) and geographically extensive sampling efforts when studying taxa that have been introduced globally and that are likely to hide species complexes.