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 suggest that habitat heterogeneity promotes food-web complexity in terms of number of species and link density. Our analyses reveal that part of the variation in food-web structure along the environmental gradients is related to species turnover, however the higher interaction turnover compared to species turnover along these gradients indicates a consistent modification of the food-web structure along environmental gradients. This could indicate that interacting species co-vary in space. In conclusion, our study shows how environmental heterogeneity via environmental filtering, not only drives turnover in species composition, but also how it influences the structure of food webs over large spatial scales.