The inadvertent introduction of the fire ant Solenopsis invicta to the United States from South America provides the opportunity to study recent social evolution by comparing social organization in native and introduced populations. We report that several important elements of social organization in multiple-queen nests differ consistently and dramatically between ants in Argentina and the United States. Colonies in Argentina contain relatively few queens and they are close relatives, whereas colonies in the United States contain high numbers of unrelated queens. A corollary of these differences is that workers in the native populations are significantly related to the new queens that they rear in contrast to the zero relatedness between workers and new queens in the introduced populations. The observed differences in queen number and relatedness signal a shift in the breeding biology of the introduced ants that is predicted on the basis of the high population densities in the new range. An additional difference in social organization that we observed, greater proportions of permanently unmated queens in introduced than in native populations, is predicted from the loss of alleles at the sex-determining locus and consequent skewing of operational sex ratios in the colonizing ants. Thus, significant recent social evolution in fire ants is consistent with theoretical expectations based on the altered ecology and population genetics of the introduced populations.