Genetic variation within the male specific portion of the Y chromosome (MSY) can clarify the origins of contemporary populations, but previous studies were hampered by partial genetic information. Population sequencing of 1,204 Sardinian males identified 11,763 MSY single nucleotide polymorphisms (SNPs), of which 6,751 have not previously been observed. We constructed a MSY phylogenetic tree containing all main haplogroups found in Europe along with many Sardinian-specific lineage clusters within each haplogroup. The tree was calibrated with archaeological data from the initial expansion of the Sardinian population ~7,700 years ago. The ages of nodes highlight different genetic strata in Sardinia and reveal presumptive timing of coalescence with other human populations. We calculate a putative age for coalescence of ~180-200,000 years ago, consistent with previous mitochondrial DNA (mtDNA) based estimates.