Males of most migratory organisms, including many birds, precede female conspecifics on their journey to the breeding areas. Several hypotheses have been proposed to explain the evolution of protandrous migration, yet they have rarely been tested at the interspecific level. Here, we provide correlational support for the "mate opportunity" hypothesis, which assumes that selection favours protandry in polygynous species where males gain significant fitness benefits from arriving earlier than females. Drawing on phenological data collected at two northern European stopover sites, we show that the time-lag in spring passage between males and females of five Palearctic migratory songbird species is positively associated with levels of extrapair paternity available from the literature. This suggests that males arrive relatively more in advance of females in species with high sperm competition where sexual selection through female choice is intense. Thus, protandry may arise from selection on the relative arrival timing of males and females rather than from selection within one of the sexes.