The Y-chromosome haplogroup composition of the population of the Cabo Verde Archipelago was profiled by using 32 single-nucleotide polymorphism markers and compared with potential source populations from Iberia, west Africa, and the Middle East. According to the traditional view, the major proportion of the founding population of Cabo Verde was of west African ancestry with the addition of a minor fraction of male colonizers from Europe. Unexpectedly, more than half of the paternal lineages (53.5%) of Cabo Verdeans clustered in haplogroups I, J, K, and R1, which are characteristic of populations of Europe and the Middle East, while being absent in the probable west African source population of Guiné-Bissau. Moreover, a high frequency of J* lineages in Cabo Verdeans relates them more closely to populations of the Middle East and probably provides the first genetic evidence of the legacy of the Jews. In addition, the considerable proportion (20.5%) of E3b(xM81) lineages indicates a possible gene flow from the Middle East or northeast Africa, which, at least partly, could be ascribed to the Sephardic Jews. In contrast to the predominance of west African mitochondrial DNA haplotypes in their maternal gene pool, the major west African Y-chromosome lineage E3a was observed only at a frequency of 15.9%. Overall, these results indicate that gene flow from multiple sources and various sex-specific patterns have been important in the formation of the genomic diversity in the Cabo Verde islands.