The structural organization of mutualism networks, typified by interspecific positive interactions, is important to maintain community diversity. However, there is little information available about the effect of introduced species on the structure of such networks. We compared uninvaded and invaded ecological communities, to examine how two species of invasive plants with large and showy flowers (Carpobrotus affine acinaciformis and Opuntia stricta) affect the structure of Mediterranean plant-pollinator networks. To attribute differences in pollination to the direct presence of the invasive species, areas were surveyed that contained similar native plant species cover, diversity and floral composition, with or without the invaders. Both invasive plant species received significantly more pollinator visits than any native species and invaders interacted strongly with pollinators. Overall, the pollinator community richness was similar in invaded and uninvaded plots, and only a few generalist pollinators visited invasive species exclusively. Invasive plants acted as pollination super generalists. The two species studied were visited by 43% and 31% of the total insect taxa in the community, respectively, suggesting they play a central role in the plant-pollinator networks. Carpobrotus and Opuntia had contrasting effects on pollinator visitation rates to native plants: Carpobrotus facilitated the visit of pollinators to native species, whereas Opuntia competed for pollinators with native species, increasing the nestedness of the plant-pollinator network. These results indicate that the introduction of a new species to a community can have important consequences for the structure of the plant-pollinator network.