There has been a recent appreciation of the ecological impacts of zooplanktonic species invasions. The North American brine shrimp Artemia franciscana is one such alien invader in hyper-saline water ecosystems at a global scale. It has been shown to outcompete native Artemia species, leading to their local extinction. We used partial sequences of the mitochondrial Cytochrome c Oxidase Subunit 1 (COI or cox1) gene to investigate the genetic diversity and phylogeography of A. salina, an extreme halophilic sexual brine shrimp, over its known distribution range (Mediterranean Basin and South Africa) and to assess the extent of local endemism, the degree of population structure and the potential impact of traditional human saltpan management on this species. We also examined the phylogenetic relationships in the genus Artemia using COI sequences. Our results show extensive regional endemism and indicate an early Pleistocene expansion of A. salina in the Mediterranean Basin. Subsequent population isolation in a mosaic of Pleistocene refugia is suggested, with two or three refugia located in the Iberian Peninsula. Two instances of long-distance colonization were also observed. Surprisingly, given its strong phylogeographical structure, A. salina showed a signature of correlation between geographical and genetic distance. Owing to strong 'priority effects', extensive population differentiation is retained, despite dispersal via migrant birds and human management of saltpans. The foreseeable expansion of A. franciscana is likely to be followed by substantial loss of genetic diversity in Mediterranean A. salina. Large genetic divergences between Mediterranean and South African A. salina suggest that the latter deserves species status.