Domesticated cattle were one of the cornerstones of European Neolithisation and are thought to have been introduced to Europe from areas of aurochs domestication in the Near East. This is consistent with mitochondrial DNA (mtDNA) data, where a clear separation exists between modern European cattle and ancient specimens of British aurochsen. However, we show that Y chromosome haplotypes of north European cattle breeds are more similar to haplotypes from ancient specimens of European aurochsen, than to contemporary cattle breeds from southern Europe and the Near East. There is a sharp north-south gradient across Europe among modern cattle breeds in the frequencies of two distinct Y chromosome haplotypes; the northern haplotype is found in 20 out of 21 European aurochsen or early domestic cattle dated 9500-1000 BC. This indicates that local hybridization with male aurochsen has left a paternal imprint on the genetic composition of modern central and north European breeds. Surreptitious mating between aurochs bulls and domestic cows may have been hard to avoid, or may have occurred intentionally to improve the breeding stock. Rather than originating from a few geographical areas only, as indicated by mtDNA, our data suggest that the origin of domestic cattle may be far more complex than previously thought.