To shed light on the structure of the basal backbone of the human Y chromosome phylogeny, we sequenced about 200 kb of the male-specific region of the human Y chromosome (MSY) from each of seven Y chromosomes belonging to clades A1, A2, A3, and BT. We detected 146 biallelic variant sites through this analysis. We used these variants to construct a patrilineal tree, without taking into account any previously reported information regarding the phylogenetic relationships among the seven Y chromosomes here analyzed. There are several key changes at the basal nodes as compared with the most recent reference Y chromosome tree. A different position of the root was determined, with important implications for the origin of human Y chromosome diversity. An estimate of 142 KY was obtained for the coalescence time of the revised MSY tree, which is earlier than that obtained in previous studies and easier to reconcile with plausible scenarios of modern human origin. The number of deep branchings leading to African-specific clades has doubled, further strengthening the MSY-based evidence for a modern human origin in the African continent. An analysis of 2204 African DNA samples showed that the deepest clades of the revised MSY phylogeny are currently found in central and northwest Africa, opening new perspectives on early human presence in the continent.