Supergenes are clusters of linked genetic loci that jointly affect the expression of complex phenotypes, such as social organization. Little is known about the origin and evolution of these intriguing genomic elements. Here we analyse whole-genome sequences of males from native populations of six fire ant species and show that variation in social organization is under the control of a novel supergene haplotype (termed Sb), which evolved by sequential incorporation of three inversions spanning half of a 'social chromosome'. Two of the inversions interrupt protein-coding genes, resulting in the increased expression of one gene and modest truncation in the primary protein structure of another. All six socially polymorphic species studied harbour the same three inversions, with the single origin of the supergene in their common ancestor inferred by phylogenomic analyses to have occurred half a million years ago. The persistence of Sb along with the ancestral SB haplotype through multiple speciation events provides a striking example of a functionally important trans-species social polymorphism presumably maintained by balancing selection. We found that while recombination between the Sb and SB haplotypes is severely restricted in all species, a low level of gene flux between the haplotypes has occurred following the appearance of the inversions, potentially mitigating the evolutionary degeneration expected at genomic regions that cannot freely recombine. These results provide a detailed picture of the structural genomic innovations involved in the formation of a supergene controlling a complex social phenotype.