Analyses of archeological, anatomical, linguistic, and genetic data suggested consistently the presence of a significant boundary between the populations of north and south in China. However, the exact location and the strength of this boundary have remained controversial. In this study, we systematically explored the spatial genetic structure and the boundary of north-south division of human populations using mtDNA data in 91 populations and Y-chromosome data in 143 populations. Our results highlight a distinct difference between spatial genetic structures of maternal and paternal lineages. A substantial genetic differentiation between northern and southern populations is the characteristic of maternal structure, with a significant uninterrupted genetic boundary extending approximately along the Huai River and Qin Mountains north to Yangtze River. On the paternal side, however, no obvious genetic differentiation between northern and southern populations is revealed.