In the present study we have analyzed 44 Y-chromosome biallelic polymorphisms in population samples from northwestern (NW) Africa and the Iberian Peninsula, which allowed us to place each chromosome unequivocally in a phylogenetic tree based on >150 polymorphisms. The most striking results are that contemporary NW African and Iberian populations were found to have originated from distinctly different patrilineages and that the Strait of Gibraltar seems to have acted as a strong (although not complete) barrier to gene flow. In NW African populations, an Upper Paleolithic colonization that probably had its origin in eastern Africa contributed 75% of the current gene pool. In comparison, ∼78% of contemporary Iberian Y chromosomes originated in an Upper Paleolithic expansion from western Asia, along the northern rim of the Mediterranean basin. Smaller contributions to these gene pools (constituting 13% of Y chromosomes in NW Africa and 10% of Y chromosomes in Iberia) came from the Middle East during the Neolithic and, during subsequent gene flow, from Sub-Saharan to NW Africa. Finally, bidirectional gene flow across the Strait of Gibraltar has been detected: the genetic contribution of European Y chromosomes to the NW African gene pool is estimated at 4%, and NW African populations may have contributed 7% of Iberian Y chromosomes. The Islamic rule of Spain, which began in a.d. 711 and lasted almost 8 centuries, left only a minor contribution to the current Iberian Y-chromosome pool. The high-resolution analysis of the Y chromosome allows us to separate successive migratory components and to precisely quantify each historical layer.