Background: Diversity patterns of livestock species are informative to the history of agriculture and indicate uniqueness of breeds as relevant for conservation. So far, most studies on cattle have focused on mitochondrial and autosomal DNA variation. Previous studies of Y-chromosomal variation, with limited breed panels, identified two Bos taurus (taurine) haplogroups (Y1 and Y2; both composed of several haplotypes) and one Bos indicus (indicine/zebu) haplogroup (Y3), as well as a strong phylogeographic structuring of paternal lineages. Methodology and Principal Findings: Haplogroup data were collected for 2087 animals from 138 breeds. For 111 breeds, these were resolved further by genotyping microsatellites INRA189 (10 alleles) and BM861 (2 alleles). European cattle carry exclusively taurine haplotypes, with the zebu Y-chromosomes having appreciable frequencies in Southwest Asian populations. Y1 is predominant in northern and north-western Europe, but is also observed in several Iberian breeds, as well as in Southwest Asia. A single Y1 haplotype is predominant in north-central Europe and a single Y2 haplotype in central Europe. In contrast, we found both Y1 and Y2 haplotypes in Britain, the Nordic region and Russia, with the highest Ychromosomal diversity seen in the Iberian Peninsula. Conclusions: We propose that the homogeneous Y1 and Y2 regions reflect founder effects associated with the development and expansion of two groups of dairy cattle, the pied or red breeds from the North Sea and Baltic coasts and the spotted, yellow or brown breeds from Switzerland, respectively. The present Y1-Y2 contrast in central Europe coincides with historic, linguistic, religious and cultural boundaries.