Zhuang, the largest ethnic minority population in China, is one of the descendant groups of the ancient Bai-Yue. Linguistically, Zhuang languages are grouped into northern and southern dialects. To characterize its genetic structure, 13 East Asian-specific Y-chromosome biallelic markers and 7 Y-chromosome short tandem repeat (STR) markers were used to infer the haplogroups of Zhuang populations. Our results showed that O*, O2a, and O1 are the predominant haplogroups in Zhuang. Frequency distribution and principal component analysis showed that Zhuang was closely related to groups of Bai-Yue origin and therefore was likely to be the descendant of Bai-Yue. The results of principal component analysis and hierarchical clustering analysis contradicted the linguistically derived north-south division. Interestingly, a west-east clinal trend of haplotype frequency changes was observed, which was supported by AMOVA analysis that showed that between-population variance of east-west division was larger than that of north-south division. O* network suggested that the Hongshuihe branch was the center of Zhuang. Our study suggests that there are three major components in Zhuang. The O* and O2a constituted the original component; later, O1 was brought into Zhuang, especially eastern Zhuang; and finally, northern Han population brought O3 into the Zhuang populations.