Climate change can shape evolution directly by altering abiotic conditions or indirectly by modifying habitats, yet few studies have investigated the effects of climate-driven habitat change on contemporary evolution. We resampled populations of Threespine Stickleback (Gasterosteus aculeatus) along a latitudinal gradient in California bar-built estuaries to examine their evolution in response to changing climate and habitat. We took advantage of the strong association between stickleback lateral plate phenotypes and Ectodysplasin A (Eda) genotypes to infer changes in allele frequencies over time. Results show that the frequency of low-plated alleles has generally increased and heterozygosity has decreased over time. Latitudinal patterns in stickleback plate phenotypes suggest that evolution at Eda is a response to climate-driven habitat transformation rather than a direct consequence of climate. As climate change has reduced precipitation and increased temperature and drought, bar-built estuaries have transitioned from lotic (flowing-water) to lentic (still-water) habitats, where the low-plated allele is favored. The low-plated allele has achieved fixation at the driest, hottest southernmost sites, a trend that is progressing northward with climate change. Climate-driven habitat change is therefore causing a reduction in genetic variation that may hinder future adaptation for populations facing multiple threats.