Due to its rapid spread and association with the numerous outbreaks, the global spread of East Asian lineage of Mycobacterium tuberculosis strains presents a global concern. Although there were many attempts to describe its population structure, no consensus has been reached yet. To define unbiased classification that will facilitate future studies of this lineage, we analyzed the performance and congruence of eight different genotyping schemes based on phylogenetic analysis of 1,398 strains from 32 countries using whole-genome sequencing (WGS) data. We confirm that East Asian lineage comprises two major clades, designated proto-Beijing, which harbors unusual 43-signal spoligoprofile, and Beijing, with well-known spoligoprofile (deleted signals from 1 to 34). We show that different genotyping methods give high consistency results in description of ancient Beijing strains while the classification of modern Beijing strains is significantly divergent due to star-shaped phylogeny. Using WGS data we intersect different studies and for the first time provide balanced classification with well-defined major groups and their genetic markers. Our reconstructed phylogenetic tree can also be used for further analysis of epidemiologically important clusters and their ancestors as well as white spots of unclassified strains, which are prospective areas of research.