Introduced species can alter the topology of food webs. For instance, an introduction can aid the arrival of free-living consumers using the new species as a resource, while new parasites may also arrive with the introduced species. Food-web responses to species additions can thus be far more complex than anticipated. In a subarctic pelagic food web with free-living and parasitic species, two fish species (arctic charr Salvelinus alpinus and three-spined stickleback Gasterosteus aculeatus) have known histories as deliberate introductions. The effects of these introductions on the food web were explored by comparing the current pelagic web with a heuristic reconstruction of the pre-introduction web. Extinctions caused by these introductions could not be evaluated by this approach. The introduced fish species have become important hubs in the trophic network, interacting with numerous parasites, predators and prey. In particular, five parasite species and four predatory bird species depend on the two introduced species as obligate trophic resources in the pelagic web and could therefore not have been present in the pre-introduction network. The presence of the two introduced fish species and the arrival of their associated parasites and predators increased biodiversity, mean trophic level, linkage density, and nestedness; altering both the network structure and functioning of the pelagic web. Parasites, in particular trophically transmitted species, had a prominent role in the network alterations that followed the introductions.