The structure of plant-pollinator networks has been claimed to be resilient to changes in species composition due to the weak degree of dependence among mutualistic partners. However, detailed empirical investigations of the consequences of introducing an alien plant species into mutualistic networks are lacking. We present the first cross-European analysis by using a standardized protocol to assess the degree to which a particular alien plant species (i.e. Carpobrotus affine acinaciformis, Impatiens glandulifera, Opuntia stricta, Rhododendron ponticum and Solanum elaeagnifolium) becomes integrated into existing native plant-pollinator networks, and how this translates to changes in network structure. Alien species were visited by almost half of the pollinator species present, accounting on average for 42 per cent of the visits and 24 per cent of the network interactions. Furthermore, in general, pollinators depended upon alien plants more than on native plants. However, despite the fact that invaded communities received more visits than uninvaded communities, the dominant role of alien species over natives did not translate into overall changes in network connectance, plant linkage level and nestedness. Our results imply that although supergeneralist alien plants can play a central role in the networks, the structure of the networks appears to be very permeable and robust to the introduction of invasive alien species into the network.