A total of 553 Y-chromosomes were analyzed from mainland Portugal and the North Atlantic Archipelagos of Açores and Madeira, in order to characterize the genetic composition of their male gene pool. A large majority (78-83% of each population) of the male lineages could be classified as belonging to three basic Y chromosomal haplogroups, R1b, J, and E3b. While R1b, accounting for more than half of the lineages in any of the Portuguese sub-populations, is a characteristic marker of many different West European populations, haplogroups J and E3b consist of lineages that are typical of the circum-Mediterranean region or even East Africa. The highly diverse haplogroup E3b in Portuguese likely combines sub-clades of distinct origins. The present composition of the Y chromosomes in Portugal in this haplogroup likely reflects a pre-Arab component shared with North African populations or testifies, at least in part, to the influence of Sephardic Jews. In contrast to the marginally low sub-Saharan African Y chromosome component in Portuguese, such lineages have been detected at a moderately high frequency in our previous survey of mtDNA from the same samples, indicating the presence of sex-related gene flow, most likely mediated by the Atlantic slave trade.