Sequence diversity and the ages of the deepest nodes of the MSY phylogeny remain largely unexplored due to the severely biased collection of SNPs available for study. We characterized 68 worldwide Y chromosomes by high-coverage next-generation sequencing, including 18 deep-rooting ones, and identified 2386 SNPs, 80% of which were novel. Many aspects of this pool of variants resembled the pattern observed among genome-wide de novo events, suggesting that in the MSY, a large proportion of newly arisen alleles has survived in the phylogeny. Some degree of purifying selection emerged in the form of an excess of private missense variants. Our tree recapitulated the previously known topology, but the relative lengths of major branches were drastically modified and the associated node ages were remarkably older. We found significantly different branch lengths when comparing the rare deep-rooted A1b African lineage with the rest of the tree. Our dating results and phylogeography led to the following main conclusions: (1) Patrilineal lineages with ages approaching those of early AMH fossils survive today only in central-western Africa; (2) only a few evolutionarily successful MSY lineages survived between 160 and 115 kya; and (3) an early exit out of Africa (before 70 kya), which fits recent western Asian archaeological evidence, should be considered. Our experimental design produced an unbiased resource of new MSY markers informative for the initial formation of the anatomically modern human gene pool, i.e., a period of our evolution that had been previously considered to be poorly accessible with paternally inherited markers.