Mutualistic networks, such as plant–pollinator networks, have attracted increasing attention in the ecological literature in the last decades, not only because of their fascinating natural history, but also because mutualistic interactions have been shown to play a key role in the maintenance of biodiversity. Although inter-specific competition has long been known to be a crucial driver of species coexistence as well, there is a lack of theory investigating the interplay between the structures of competitive and mutualistic networks when jointly considered. Here, we develop an analytical framework to study the structural stability — the range of conditions under which all species coexist stably, i.e. where the community is both feasible and stable — of ecological communities in which both mutualistic interactions between plants and pollinators and competitive interactions among plants and among pollinators are present. Using the structure of 50 real networks for mutualistic interactions, combined with analytical and numerical analyses, we show that the structure of the competitive network radically alters the necessary conditions for species coexistence in these communities. Our mathematical framework also allows to accurately characterize the structural stability of these systems. Moreover, we introduce a new metric that accurately links the network structures of competitive and mutualistic interactions to species coexistence. Our results highlight the joint role of the structures of different interaction types to understand the stability of ecological communities and facilitate the analysis of similar natural and artificial systems in which mutualism and competition coexist.