Austronesian diffusion is considered one of the greatest dispersals in human history; it led to the peopling of an extremely vast region, ranging from Madagascar in the Indian Ocean to Easter Island in Remote Oceania. The Y-chromosome haplogroup O3a2b*-P164(xM134), a predominant paternal lineage of Austronesian populations, is found at high frequencies in Polynesian populations. However, the internal phylogeny of this haplogroup remains poorly investigated. In this study, we analyzed -seventeen Y-chromosome sequences of haplogroup O3a2b*-P164(xM134) and generated a revised phylogenetic tree of this lineage based on 310 non-private Y-chromosome polymorphisms. We discovered that all available O3a2b*-P164(xM134) samples belong to the newly defined haplogroup O3a2b2-N6 and samples from Austronesian populations belong to the sublineage O3a2b2a2-F706. Additionally, we genotyped a series of Y-chromosome polymorphisms in a large collection of samples from China. We confirmed that the sublineage O3a2b2a2b-B451 is unique to Austronesian populations. We found that O3a2b2-N6 samples are widely distributed on the eastern coastal regions of Asia, from Korea to Vietnam. Furthermore, we propose- that the O3a2b2a2b-B451 lineage represents a genetic connection between ancestors of Austronesian populations and ancient populations in North China, where foxtail millet was domesticated about 11,000 years ago. The large number of newly defined Y-chromosome polymorphisms and the revised phylogenetic tree of O3a2b2-N6 will be helpful to explore the origin of proto-Austronesians and the early diffusion process of Austronesian populations.