The mating system of the honeybee (Apis mellifera) has been regarded as one of the most panmictic in the animal kingdom, with thousands of males aggregating in drone congregation areas (DCAs) that virgin queens visit to mate with tens of partners. Although males from many colonies gather at such congregations, the temporal changes in the colonies contributing drones remain unknown. Yet, changes in the DCAs' genetic structure will ultimately determine population gene flow and effective population size. By repeatedly sampling drones from an African DCA over a period of 3 years, we studied the temporal changes in the genetic structure of a wild honeybee population. Using three sets of tightly linked microsatellite markers, we were able to reconstruct individual queen genotypes with a high accuracy, follow them through time and estimate their rate of replacement. The number of queens contributing drones to the DCA varied from 12 to 72 and was correlated with temperature and rainfall. We found that more than 80% of these queens were replaced by mostly unrelated ones in successive eight months sampling intervals, which resulted in a clear temporal genetic differentiation of the DCA. Our results suggest that the frequent long-range migration of colonies without nest-site fidelity is the main driver of this high queen turnover. DCAs of African honeybees should thus be regarded as extremely dynamic systems which together with migration boost the effective population size and maintain a high genetic diversity in the population.