Climate and land use change can alter the incidence and strength of biotic interactions, with important effects on the distribution, abundance and function of species. To assess the importance of these effects and their dynamics, studies quantifying how biotic interactions change in space and time are needed. We studied interactions between nettle-feeding butterflies and their shared natural enemies (parasitoids) locally and across 500 km latitudinal gradient in Sweden. We also examined the potential impact of the range-expansion of the butterfly Araschnia levana on resident butterflies via shared parasitoids, by studying how parasitism in resident butterflies covaries with the presence or absence of the newly-established species. We collected 6777 larvae of four nettle-feeding butterfly species (Aglais urticae, Aglais io, Ar. levana and Vanessa atalanta), over two years, at 19 sites distributed along the gradient. We documented the parasitoid complex for each butterfly species and measured their overlap, and analysed how parasitism rates were affected by butterfly species assemblage, variations in abundance, time, and the arrival of Ar. levana. Parasitoids caused high mortality, with substantial overlap in the complex of parasitoids associated with the four host butterflies. Levels of parasitism differed significantly among butterflies and were influenced by the local butterfly species assemblage. Our results also suggest that parasitism in resident butterflies is elevated at sites where Ar. levana has been established for a longer period. In our study system, variations in butterfly species assemblages were associated in a predictable way with substantial variations in rates of parasitism. This relationship is likely to affect the dynamics of the butterfly host species, and potentially cascade to the larger number of species with which they interact. These results highlight the importance of indirect interactions and their potential to reorganise ecological communities, especially in the context of shifts in species distributions in a warmer world.