Anthropogenically driven climatic change is expected to reshape global patterns of species distribution and abundance. Given recent links between genetic variation and environmental patterns, climate change may similarly impact genetic population structure, but we lack information on the spatial and mechanistic underpinnings of genetic-climate associations. Here, we show that current genetic variability of Canada lynx (Lynx canadensis) is strongly correlated with a winter climate gradient (i.e. increasing snow depth and winter precipitation from west-to-east) across the Pacific-North American (PNO) to North Atlantic Oscillation (NAO) climatic systems. This relationship was stronger than isolation by distance and not explained by landscape variables or changes in abundance. Thus, these patterns suggest that individuals restricted dispersal across the climate boundary, likely in the absence of changes in habitat quality. We propose habitat imprinting on snow conditions as one possible explanation for this unusual phenomenon. Coupling historical climate data with future projections, we also found increasingly diverging snow conditions between the two climate systems. Based on genetic simulations using projected climate data (2041-2070), we predicted that this divergence could lead to a threefold increase in genetic differentiation, potentially leading to isolated east-west populations of lynx in North America. Our results imply that subtle genetic structure can be governed by current climate and that substantive genetic differentiation and related ecological divergence may arise from changing climate patterns.