The evolution of eusociality has allowed ants to become one of the most conspicuous and ecologically dominant groups of organisms in the world. A large majority of the current ~14,000 ant species belong to the formicoids1, a clade of nine subfamilies which exhibit the most extreme forms of reproductive division of labour, large colony size2, worker polymorphism3 and extended queen longevity4. The eight remaining non-formicoid subfamilies are less well studied, with few genomes having been sequenced so far and unclear phylogenetic relationships5. By sequencing 65 genomes, we provide a robust phylogeny of the 17 ant subfamilies, retrieving high support to the controversial leptanillomorph clade (Leptanillinae and Martialinae) as the sister-group to all other extant ants. Moreover, our genomic analyses revealed that the emergence of the formicoids was accompanied by an elevated number of positive selection events. Importantly, the top three gene functions under selection are linked to key features of complex eusociality with histone acetylation being implicated in caste differentiation, gene silencing by RNA in worker sterility and autophagy in longevity. These results show that key pathways associated with eusociality have been under strong selection during the Cretaceous, suggesting that the molecular foundations of complex eusociality may have evolved rapidly in less than 20 Ma.