Gene flow and demographic history can play important roles in the adaptive genetic differentiation of species, which is rarely understood in the high-altitude adaptive evolution of birds. To elucidate genetic divergence of populations in the great tit complex (Parus major, P. minor and P. cinereus) at different elevations, we compared the genetic structure and gene flow in hemoglobin genes with neutral loci. Our results revealed the elevationally divergent structure of alpha(A)-globin gene, distinctive from that of the beta(A)-globin gene and neutral loci. We further investigated gene flow patterns among the populations in the central-northern (>1,000 ma.s.l.), south-eastern (<1,000 m a.s.l.) regions and the Southwest Mountains (>2,000 m a.s.l.) in China. The high-altitude (>1,000 m a.s.l.) diverged alpha(A)-globin genetic structure coincided with higher alpha(A)-globin gene flow between highland populations, in contrast to restricted neutral gene flow concordant with the phylogeny. The higher alpha(A)-globin gene flow suggests the possibility of adaptive evolution during population divergence, contrary to the lower a alpha(A)-globin gene flow homogenized by neutral loci during population expansion. In concordance with patterns of historical gene flow, genotypic and allelic profiles provide distinctive patterns of fixation in different high-altitude populations. The fixation of alleles at contrasting elevations may primarily due to highland standing variants alpha(A)49Asn/72Asn/108Ala originating from the south-western population. Our findings demonstrate a pattern of genetic divergence with gene flow in major hemoglobin genes depending on population demographic history.