High recombination rates have previously been detected in two groups of eusocial insects; honeybees and ants. In this study we estimate recombination rate in a eusocial wasp Vespula vulgaris that represents a third phylogenetic lineage within eusocial hymenopterans. A genetic linkage map of V. vulgaris based on 210 markers shows that the total map length is 2129 cM and the recombination rate is 9.7 cM/Mb (or 103 kb/cM). The present estimate in V. vulgaris is somewhat smaller than in the honeybee Apis mellifera and intermediate between the estimates from two ant species (Acromyrmex echinatior, Pogonomyrmex rugosus). Altogether, the estimates from these eusocial species are higher than in any other insect reported so far. The four species (V. vulgaris, A. mellifera, A. echinatior, P. rugosus) are characterized by advanced eusociality with large colonies, clear queen-worker dimorphism and well developed task specialization. They also have colonies with a single, normally multiply inseminated (polyandrous) queen. Benefits of genotypic diversity within colonies (e.g. through improved task specialization or pathogen and parasite resistance) may have selected for both polyandry and high recombination rate in such advanced eusocial insects.