Variation in paternity frequency in colonies of eusocial insects has profound effects on the relatedness among offspring and on the genetic diversity of colonies. Data on queen `mating-frequency' in eusocial Hymenoptera vary in both quality and the phase of the `mating' process they address. Some are observational studies of the range or maximum number of copulations; others are derived from estimates of the number of sperm in males and queens; others use genetic techniques to determine the paternity of different males among female offspring. Only the latter data can be used to calculate relatedness among offspring females. Previous reviews drew attention to these problems, but their results have established the impression that high paternity frequencies are common, largely because multiple copulations are frequently observed. For ants, we show that: (i) the range of observed copulations overestimates effective paternity frequency; and (ii) the mean effective paternity frequency in 19 species, for which accurate data based on allozyme analysis of mother - offspring combinations are available, is only 1.16 (range 1-1.48). Over one third of these species have queens in which only one male contributes to paternity. Data from 34 species, which include less detailed genetic studies and four species studied using sperm counts, give similar results. Only two species, both Atta leaf cutter ants and both studied using data on sperm stored in queen spermathecas, appear to have effective insemination frequencies above two. Data on bees and wasps show a similar trend. We conclude that reliably documented high paternity or insemination frequencies (> 2) are currently restricted to one phylogenetically isolated and highly eusocial taxon each in ants, eusocial bees and wasps (Atta, Apis and Vespula, respectively). This pattern justifies the working hypothesis that multiple mating, by lowering the relatedness between female offspring and thereby the benefits of reproductive helping behaviour, has not been a general constraint for the evolution of eusociality in the Hymenoptera. Using reliable data on paternity frequency and insemination, we re-analyse two factors that it has been suggested correlate with mating frequency: colony population and number of egg-laying queens per colony. We find the following. 1. There is a significant positive correlation between paternity/insemination frequency and colony size for monogynous ants, but not for polygynous ants. This result seems to support the `sperm limitation' hypothesis, that queens which need to be highly fecund copulate multiply to store sufficient sperm. We note, however, that the same trend is expected when large and/or long-lived colonies profit more from having genetically diverse offspring. 2. There is no significant negative correlation between paternity/insemination frequency and number of queens per colony. However, when the analysis is restricted to species with large colonies and no intranidal mating, the correlation between paternity frequency and queen number becomes marginally significant. Several previous reviews have addressed the possible adaptive significance of multiple paternity. In contrast, and in keeping with the data that show single paternity to be frequent, we discuss selective reasons for single or low paternity. We compare the relative effects of multiple paternity and multiple maternity on genetic diversity within colonies and show that they are not equivalent, and we also discuss directions for future research on paternity issues in social insects.