Colonization of freshwater habitats from marine environments exposes organisms to novel combinations of temperature and salinity, but little is known about physiological responses to the interactive effects of these stressors. Here, we examined the effects of temperature (14 versus 4 °C) and salinity (11 versus 0.3 ppt) on gill gene expression in marine, anadromous, and freshwater populations of threespine stickleback (Gasterosteus aculeatus). Expression of the epithelial calcium channel was not affected by temperature or salinity, but had significantly higher expression in the freshwater ecotype. The combination of low temperature and low salinity had non-additive effects on the expression of the Na+/H+ exchanger. Fish exposed to the combination of low temperature and low salinity had expression levels similar to fish exposed to either factor in isolation. Expression of Na+,K+-ATPase α-subunit was greater in fish exposed to low temperature and low salinity than in fish exposed to the factors separately, and this effect was the most pronounced in the marine ecotype. We also examined the interactive effects of salinity and temperature on gill morphology in the marine ecotype, and observed non-additive effects. Low temperature increased the size of the interlamellar cell mass in fish held at 11 ppt, but not at 0.3 ppt, and the effect of low salinity was in the opposite direction in fish at high and low temperatures. These data demonstrate interactive effects of temperature and salinity and highlight that overwintering in cold freshwater was likely a physiological challenge for marine stickleback as they colonized freshwater following the last glaciation.