Significance: A reduction in heterozygosity may limit the opportunity for species facing the same selective pressures to evolve parallel adaptation. Examining 19 East Asian tits’ genomes, we find a pattern of lower heterozygosity in western endemics compared with that found in both eastern endemics and widespread taxa, consistent with expectations of demographic contraction driven by late-Pleistocene climate fluctuations. Comparisons among both endemic and widespread tits find disproportionate levels of genetic differentiation between pairs of lowland and highland tits in genomic regions that are enriched for genes that may be associated with the oxygen transport cascade and/or thermogenesis. However, evolution did not occur in the same genes, and populations with higher heterozygosity did not show higher levels of parallel evolution as predicted.