The peopling of East Asia by the first modern humans is strongly debated from a genetic point of view. A north-south genetic differentiation observed in this geographic area suggests different hypotheses on the origin of Northern East Asian (NEA) and Southern East Asian (SEA) populations. In this study, the highly polymorphic HLA markers were used to investigate East Asian genetic diversity. Our database covers a total of about 127,000 individuals belonging to 84 distinct Asian populations tested for HLA-A, -B, -C, -DPB1, and/or -DRB1 alleles. Many Chinese populations are represented, which have been sampled in the last 30 years but rarely taken into account in international research due to their data published in Chinese. By using different statistical methods, we found a significant correlation between genetics and geography and relevant genetic clines in East Asia. Additionally, HLA alleles appear to be unevenly distributed: some alleles observed in NEA populations are widespread at the global level, while some alleles observed in SEA populations are virtually unique in Asia. The HLA genetic variation in East Asia is also characterized by a decrease of diversity from north to south, although a reverse pattern appears when one only focuses on alleles restricted to Asia. These results reflect a more complex migration history than that illustrated by the "southern-origin" hypothesis, as genetic contribution of ancient human migrations through a northern route has probably been quite substantial. We thus suggest a new overlapping model where northward and southward opposite migrations occurring at different periods overlapped.