Mutualistic networks are key for the creation and maintenance of biodiversity, yet are threatened by global environmental change. Most simulation models assume that network structure remains static after species losses, despite theoretical and empirical reasons to expect dynamic responses. We assessed the effects of experimental single bumblebee species removals on the structure of entire flower visitation networks. We hypothesized that network structure would change following processes linking interspecific competition with dietary niche breadth. We found that single pollinator species losses impact pollination network structure: resource complementarity decreased, while resource overlap increased. Despite marginally increased connectance, fewer plant species were visited after species removals. These changes may have negative functional impacts, as complementarity is important for maintaining biodiversity–ecological functioning relationships and visitation of rare plant species is critical for maintaining diverse plant communities.