Studies of climate effects on ecology often account for non-stationarity in individual physical and biological variables, but rarely allow for non-stationary relationships among variables. Here, we show that non-stationary relationships among physical and biological variables are central to understanding climate effects on salmon (Onchorynchus spp.) in the Gulf of Alaska during 1965-2012. The relative importance of two leading patterns in North Pacific climate, the Pacific Decadal Oscillation (PDO) and North Pacific Gyre Oscillation (NPGO), changed around 1988/89 as reflected by changing correlations with leading axes of sea surface temperature variability. Simultaneously, relationships between the PDO and Gulf of Alaska environmental variables weakened, and long-standing temperature-salmon and PDO-salmon covariance declined to zero. We propose a mechanistic explanation for changing climate-salmon relationships in terms of non-stationary atmosphere-ocean interactions coinciding with changing PDO-NPGO relative importance. We also show that regression models assuming stationary climate-salmon relationships are inappropriate over the multidecadal time scale we consider. Relaxing assumptions of stationary relationships markedly improved modeling of climate effects on salmon catches and productivity. Attempts to understand the implications of changing climate patterns in other ecosystems might also be aided by the application of models that allow associations among environmental and biological variables to change over time.