Explaining cases of long-term persistence of parthenogenesis has proven an arduous task for evolutionary biologists. Interpreting sexual-asexual interactions though has recently advanced owing to methodological design, increased taxon sampling and choice of model organisms. We inferred the phylogeny of Artemia, a halophilic branchiopod genus of sexual and parthenogenetic forms with cosmopolitan distribution, marked geographic patterns and ecological partitioning. Joint analysis of newly derived ITS1 sequences and 16S RFLP markers from global isolates indicates significant interspecific divergence as well as pronounced diversity for parthenogens, matching that of sexual ancestors. Maximum parsimony, maximum likelihood, and Bayesian methods were largely congruent in reconstructing the phylogeny of the genus. Given the current sampling, at least four independent origins of parthenogenesis are deduced. Molecular clock calibrations based on biogeographic landmarks indicate that the lineage leading to A. persimilis diverged from the common ancestor of all Artemia species between 80 and 90 MYA at the time of separation of Africa from South America, whereas parthenogenesis first appeared at least 3 MYA. Common mitochondrial DNA haplotypes delineate A. urmiana and A. tibetiana as possible maternal parents of several clonal lineages. A novel topological placement of A. franciscana as a sister clade to all Asian Artemia and parthenogenetic forms is proposed and also supported by ITS1 length and other existing data.