The polymorphisms in the human leukocyte antigen (HLA) region are powerful tool for studying human evolutionary processes. We investigated genetic structure of Japanese by using five-locus HLA genotypes (HLA-A, -B, -C, -DRB1, and -DPB1) of 2,005 individuals from 10 regions of Japan. We found a significant level of population substructure in Japanese; particularly the differentiation between Okinawa Island and mainland Japanese. By using a plot of the principal component scores, we identified ancestry informative alleles associated with the underlying population substructure. We examined extent of linkage disequilibrium (LD) between pairs of HLA alleles on the haplotypes that were differentiated among regions. The LDs were strong and weak for pairs of HLA alleles characterized by low and high frequencies in Okinawa Island, respectively. The five-locus haplotypes whose alleles exhibit strong LD were unique to Japanese and South Korean, suggesting that these haplotypes had been recently derived from the Korean Peninsula. The alleles characterized by high frequency in Japanese compared to South Korean formed segmented three-locus haplotype that was commonly found in Aleuts, Eskimos, and North- and Meso-Americans but not observed in Korean and Chinese. The serologically equivalent haplotype was found in Orchid Island in Taiwan, Mongol, Siberia, and Arctic regions. It suggests that early Japanese who existed prior to the migration wave from the Korean Peninsula shared ancestry with northern Asian who moved to the New World via the Bering Strait land bridge. These results may support the admixture model for peopling of Japanese Archipelago.