We explored the phylogeography of human Y-chromosomal haplogroup E3b by analyzing 3401 individuals from five continents. Our data refine the phylogeny of the entire haplogroup, which appears as a collection of lineages with very different evolutionary histories, and reveal signatures of several distinct processes of migrations and/or recurrent gene flow that occurred in Africa and western Eurasia over the past 25000 years. In Europe, the overall frequency pattern of haplogroup E-M78 does not support the hypothesis of a uniform spread of people from a single parental Near Eastern population. The distribution of E-M81 chromosomes in Africa closely matches the present area of distribution of Berber-speaking populations on the continent, suggesting a close haplogroup-ethnic group parallelism. E-M34 chromosomes were more likely introduced in Ethiopia from the Near East. In conclusion, the present study shows that earlier work based on fewer Y-chromosome markers led to rather simple historical interpretations and highlights the fact that many population-genetic analyses are not robust to a poorly resolved phylogeny.