According to the inclusive fitness theory, some degree of positive relatedness is required for the evolution and maintenance of altruism. However, ant colonies are sometimes large interconnected networks of nests which are genetically homogenous entities, causing a putative problem for the theory. We studied spatial structure and genetic relatedness in two supercolonies of the ant Formica exsecta, by using nuclear and mitochondrial markers. We show that there may be multiple pathways to supercolonial social organization leading to different spatial genetic structures. One supercolony formed a genetically homogenous population dominated by a single mtDNA haplotype, as expected if founded by a small number of colonizers, followed by nest propagation by budding and domination of the habitat patch. The other supercolony had several haplotypes and the spatial genetic structure was a mosaic of nuclear and mitochondrial clusters. Genetic diversity probably originated from long-range dispersal, and the mosaic population structure is likely a result of stochastic short-range dispersal of individuals. Such a mosaic spatial structure is apparently discordant with the current knowledge about the integrity of ant colonies. Relatedness was low in both populations when estimated among nestmates, but increased significantly when estimated among individuals sharing the same genetic cluster or haplogroup. The latter association indicates the important historical role of queen dispersal in the determination of the spatial genetic structure.