Y-chromosomes from 76 Chinese men covering 33 ethnic minorities throughout China as well as the Han majority were collected as genetic material for the study of Chinese nonrecombinant Y-chromosome (NRY) phylogeny. Of the accepted worldwide NRY haplogroups, three (haplogroups D, C, O) were significant in this sample, extending previous assessments of Chinese genetic diversity. Based on geographic, linguistic, and ethnohistorical information, the 33 Chinese ethnic minorities in our survey were divided into the following four subgroups: North, Tibet, West, and South. Inferred from the distribution of the newly found immediate ancestor lineage haplogroup O*, which has M214 but not M175, we argue that the southern origin scenario of this most common Chinese Y haplogroup is not very likely. We tentatively propose a West/North-origin hypothesis, suggesting that haplogroup O originated in West/North China and mainly evolved in China and thence spread further throughout eastern Eurasia. The nested cladistic analysis revealed in detail a multilayered, multidirectional, and continuous history of ethnic admixture that has shaped the contemporary Chinese population. Our results give some new clues to the evolution and migration of the Chinese population and its subsequence moving about in this land, which are in accordance with the historical records.