Social insects rank among the most invasive of terrestrial species. The success of invasive social insects stems, in part, from the flexibility derived from their social behaviors. We used genetic markers to investigate if the social system of the invasive wasp, Vespula pensylvanica, differed in its introduced and native habitats in order to better understand variation in social phenotype in invasive social species. We found that (1) nestmate workers showed lower levels of relatedness in introduced populations than native populations, (2) introduced colonies contained workers produced by multiple queens whereas native colonies contained workers produced by only a single queen, (3) queen mate number did not differ significantly between introduced and native colonies, and (4) workers from introduced colonies were frequently produced by queens that originated from foreign nests. Thus, overall, native and introduced colonies differed substantially in social phenotype because introduced colonies more frequently contained workers produced by multiple, foreign queens. In addition, the similarity in levels of genetic variation in introduced and native habitats, as well as observed variation in colony social phenotype in native populations, suggest that colony structure in invasive populations may be partially associated with social plasticity. Overall, the differences in social structure observed in invasive V. pensylvanica parallel those in other, distantly related invasive social insects, suggesting that insect societies often develop similar social phenotypes upon introduction into new habitats.