Species are redistributing globally in response to climate warming, impacting ecosystem functions and services. In the Barents Sea, poleward expansion of boreal species and a decreased abundance of Arctic species are causing a rapid borealization of the Arctic communities. This borealization might have profound consequences on the Arctic food web by creating novel feeding interactions between previously non co-occurring species. An early identification of new feeding links is crucial to predict their ecological impact. However, detection by traditional approaches, including stomach content and isotope analyses, although fundamental, cannot cope with the speed of change observed in the region, nor with the urgency of understanding the consequences of species redistribution for the marine ecosystem. In this study, we used an extensive food web (metaweb) with nearly 2,500 documented feeding links between 239 taxa coupled with a trait data set to predict novel feeding interactions and to quantify their potential impact on Arctic food web structure. We found that feeding interactions are largely determined by the body size of interacting species, although species foraging habitat and metabolic type are also important predictors. Further, we found that all boreal species will have at least one potential resource in the Arctic region should they redistribute therein. During 2014–2017, 11 boreal species were observed in the Arctic region of the Barents Sea. These incoming species, which are all generalists, change the structural properties of the Arctic food web by increasing connectance and decreasing modularity. In addition, these boreal species are predicted to initiate novel feeding interactions with the Arctic residents, which might amplify their impact on Arctic food web structure affecting ecosystem functioning and vulnerability. Under the ongoing species redistribution caused by environmental change, we propose merging a trait-based approach with ecological network analysis to efficiently predict the impacts of range-shifting species on food webs.