The sequencing of archaic humans has transformed our understanding of human origins. Neanderthals have contributed genetic variants to modern populations, potentially influencing multiple phenotypes. However, large sections of the Neanderthal genome are not represented in the genomes of modern populations, including the Y chromosome. It has been suggested that genetic incompatibilities played a role in the isolation of archaic and modern humans. We present the analysis of ~120 kb of exome-captured Y-chromosome DNA from a Neanderthal individual from El Sidrón, Spain. Comparing this sequence with those of the human and chimpanzee references, and with those of two A00 Y chromosomes, we: 1) determined the branching order of the human lineages, 2) estimated the time to the most recent common ancestor (TMRCA) between modern human and Neanderthal lineages, and 3) assessed differences in the coding sequence of their Y chromosomes. We determined that the Neanderthal Y chromosome lineage branches out before modern human lineages diversified. The TMRCA estimate of ~588 thousand years ago, approximately doubles that of the human reference and the A00 lineage. We observed nine protein-coding changes between Neanderthal and modern human lineages, four of which (in genes PCDH11Y, TMSB4Y, USP9Y, and KDM5D) are predicted to have functional importance. Three of these four genes are known to result in male-specific minor histocompatibility antigens, and might be implicated in the reproductive isolation of Neanderthals and modern humans. We discuss the implications of our finding and our future steps.