Mycobacterium avium subsp. hominissuis (MAH) is one of the most common nontuberculous mycobacterial species responsible for chronic lung disease in humans. Despite increasing worldwide incidence, little is known about the genetic mechanisms behind the population evolution of MAH. To elucidate the local adaptation mechanisms of MAH, we assessed genetic population structure, the mutual homologous recombination, and gene content for 36 global MAH isolates, including 12 Japanese isolates sequenced in the present study. We identified five major MAH lineages and found that extensive mutual homologous recombination occurs among them. Two lineages (MahEastAsia1 and MahEastAsia2) were predominant in the Japanese isolates. We identified alleles unique to these two East Asian lineages in the loci responsible for trehalose biosynthesis (treS and mak) and in one mammalian cell entry operon, which presumably originated from as yet undiscovered mycobacterial lineages. Several genes and alleles unique to East Asian strains were located in the fragments introduced via recombination between East Asian lineages, suggesting implication of recombination in local adaptation. These patterns of MAH genomes are consistent with the signature of distribution conjugative transfer, a mode of sexual reproduction reported for other mycobacterial species.