Clonal reproduction may facilitate the spread of invasive species by reducing the minimum population size necessary for successful establishment. We used microsatellite markers to reconstruct the composition of founding populations in two regional (Central Africa and Hawaii) and 23 local (near a Gabonese oilfield) invasions of the facultatively parthenogenetic little fire ant. Central Africa had a single dominant queen clone, which appears to have initiated the regional infestation, and then produced numerous other clones by rare sexual reproduction. This interpretation of the data was also supported by the genotype of a worker from the first collection in Africa (Gabon 1913). We found only a single queen clone in Hawaii, likewise indicating a single-clone introduction, most likely from an earlier infestation in Florida. Single-clone introductions also gave rise to the vast majority (92%) of local infestations at our oilfield study site. These results suggest the unusual, largely clonal, reproductive strategy of the little fire ant may enhance its success as an invasive species. However, the occasional sexual production of novel genotypes after the initial introduction may provide genetic flexibility that overcomes shortcomings of pure clonality.