Weaver ants (Oecophylla smaragdina) are dominant ants in open forests from India, Australia, China and Southeast Asia, whose leaf nests are held together with larval silk. The species, together with its sole congener O. longinoda, has been important in research on biological control, communication, territoriality and colony integration. Over most of the range, only one queen has been found per colony, but the occurrence of several queens per nest has been reported for the Australian Northern Territory. The number of males mating with each queen is little known. Here we report on the colony structure of O. smaragdina using published and new microsatellite markers. Worker genotype arrays reflect the occurrence of habitual polygyny (more than one queen per colony) in 18 colonies from Darwin, Northern Australia, with up to five queens inferred per colony. Monogyny (one queen per colony) with occasional polygyny was inferred for 14 colonies from Queensland, Australia, and 20 colonies from Java, Indonesia. Direct genotyping of the sperm carried by 77 Queensland queens and worker genotypic arrays of established colonies yielded similar results, indicating that less than half of the queens mate only once and some mate up to five times. Worker genotype arrays indicated that queens from Java and the Northern Territory also often mate with more than one male, but less often than those from Queensland. A strong isolation-by-distance effect was found for Queensland samples. The variation uncovered means that O. smaragdina is a more versatile study system than previously supposed.