The ant Formica exsecta has two types of colonies that exist in sympatry but usually as separate subpopulations: colonies with simple social organization and single queens (M type) or colonial networks with multiple queens (P type). We used both nuclear (DNA microsatellites) and mitochondrial markers to study the transition between the social types, and the contribution of males and females in gene flow within and between the types. Our results showed that the social types had different spatial genetic structures. The M subpopulations formed a fairly uniform population, whereas the P subpopulations were, on average, more differentiated from each other than from the nearby M subpopulations and could have been locally established from the M-type colonies, followed by philopatric behavior and restricted emigration of females. Thus, the relationship between the two social types resembles that of source (M type) and sink (P type) populations. The comparison of mitochondrial (phiST) and nuclear (FST) differentiation indicates that the dispersal rate of males is four to five times larger than that of females both among the P-type subpopulations and between the social types. Our results suggest that evolution toward complex social organization can have an important effect on genetic population structure through changes in dispersal behavior associated with different sociogenetic organizations.