Large‐scale patterns in species diversity and community composition are associated with environmental gradients, but the implications of these patterns for food‐web structure are still unclear. Here, we investigated how spatial patterns in food‐web structure are associated with environmental gradients in the Barents Sea, a highly productive shelf sea of the Arctic Ocean. We compared food webs from 25 subregions in the Barents Sea and examined spatial correlations among food‐web metrics, and between metrics and spatial variability in seawater temperature, bottom depth and number of days with ice cover. Several food‐web metrics were positively associated with seawater temperature: connectance, level of omnivory, clustering, cannibalism, and high variability in generalism, while other food‐web metrics such as modularity and vulnerability were positively associated with sea ice and negatively with temperature. Food‐web metrics positively associated with habitat heterogeneity were: number of species, link density, omnivory, path length, and trophic level. This finding suggests that habitat heterogeneity promotes food‐web complexity in terms of number of species and link density. Our analyses reveal that spatial variation in food‐web structure along the environmental gradients is partly related to species turnover. However, the higher interaction turnover compared to species turnover along these gradients indicates a consistent modification of food‐web structure, implying that interacting species may co‐vary in space. In conclusion, our study shows how environmental heterogeneity, via environmental filtering, influences not only turnover in species composition, but also the structure of food webs over large spatial scales.