Endosymbioses influence host physiology, reproduction, and fitness, but these relationships require efficient microbe transmission between host generations to persist. Maternally transmitted Wolbachia are the most common known endosymbionts, but their frequencies vary widely within and among host populations for unknown reasons. Here we integrate genomic, cellular, and phenotypic analyses with mathematical models to provide an unexpectedly simple explanation for global wMel Wolbachia prevalence in Drosophila melanogaster. Cooling temperatures decrease wMel cellular abundance at a key stage of host oogenesis, producing temperature-dependent variation in maternal transmission that plausibly explains latitudinal clines of wMel frequencies on multiple continents. wMel sampled from a temperate climate targets the germline more efficiently in the cold than a recently differentiated tropical variant (~2,200 years ago), indicative of rapid wMel adaptation to climate. Genomic analyses identify a very narrow list of wMel alleles—most notably, a derived stop codon in the major Wolbachia surface protein WspB—that underlie thermal sensitivity of cellularWolbachia abundance and covary with temperature globally. Decoupling temperate wMel and host genomes further reduces transmission in the cold, a pattern that is characteristic of host-microbe co-adaptation to a temperate climate. Complex interactions among Wolbachia, hosts, and the environment (GxGxE) mediate wMel cellular abundance and maternal transmission, implicating temperature as a key determinant of Wolbachia spread and equilibrium frequencies, in conjunction with Wolbachia effects on host fitness and reproduction. Our results motivate strategic use of locally selected wMel variants for Wolbachia-based biocontrol efforts, which currently protect millions of individuals from arboviruses that cause human disease.