Army ants have long been suspected to represent an independent origin of multiple queen-mating in the social Hymenoptera. Using microsatellite markers, we show that queens of the African army ant Dorylus (Anomma) molestus have the highest absolute (17.3) and effective (17.5) queen-mating frequencies reported so far for ants. This confirms that obligate multiple queen-mating in social insects is associated with large colony size and advanced social organization, but also raises several novel questions. First, these high estimates place army ants in the range of mating frequencies of honeybees, which have so far been regarded as odd exceptions within the social Hymenoptera. Army ants and honeybees are fundamentally different in morphology and life history, but are the only social insects known that combine obligate multiple mating with reproduction by colony fission and extremely male-biased sex ratios. This implies that the very high numbers of matings in both groups may be due partly to the relatively low costs of additional matings. Second, we were able to trace recent events of colony fission in four of the investigated colonies, where the genotypes of the two queens were only compatible with a mother-daughter relationship. A direct comparison of male production between colonies with offspring from one and two queens, respectively, suggested strongly that new queens do not produce a sexual brood until all workers of the old queen have died, which is consistent with kin selection theory.