We studied population genetic variation and structure in the fire ant Solenopsis invicta using nuclear genotypic and mitochondrial DNA (mtDNA) sequence data obtained from samples collected throughout its native range. Geographic populations are strongly differentiated at both genomes, with such structure more pronounced in Brazil than in Argentina. Higher-level regional structure is evident from the occurrence of isolation-by-distance patterns among populations, the recognition of clusters of genetically similar, geographically adjacent populations by ordination analysis, and the detection of an mtDNA discontinuity between Argentina and Brazil coinciding with a previously identified landform of biogeographical relevance. Multiple lines of evidence from both genomes suggest that the ancestors of the ants we studied resembled extant northern Argentine S. invicta, and that existing Brazilian populations were established more recently by serial long-distance colonizations and/or range expansions. The most compelling evidence for this is the corresponding increase in F-K (a measure of divergence from a hypothetical ancestor) and decrease in genetic diversity with distance from the Corrientes population in northern Argentina. Relatively deep sequence divergence among several mtDNA clades, coupled with geographical partitioning of many of them, suggests prolonged occupation of South America by S. invicta in more-or-less isolated regional populations. Such populations appear, in some cases, to have come into secondary contact without regaining the capacity to freely interbreed. We conclude that nominal S. invicta in its native range comprises multiple entities that are sufficiently genetically isolated and diverged to have embarked on independent evolutionary paths.