Pollination networks are representations of all interactions between co-existing plants and their flower visiting animals at a given site. Although the study of networks has become a distinct sub-discipline in pollination biology, few studies have attempted to quantify spatio-temporal variation in species composition and structure of networks. We here investigate patterns of year-to-year change in pollination networks from six different sites spanning a large latitudinal gradient. We quantified level of species persistence and interactions among years, and examined year-to-year variation of network structural parameters in relation to latitude and sampling effort. In addition, we tested for correlations between annual variation in network parameters and short and long-term climate change variables. Numbers of plant and animal species and interactions were roughly constant from one year to another at all sites. However, composition of species and interactions changed from one year to another. Turnover was particularly high for flower visitors and interactions. On the other hand, network structural parameters (connectance, nestedness, modularity and centralization) remained remarkably constant between years, regardless of network size and latitude. Inter-annual variation of network parameters was not related to short or long term variation in climate variables (mean annual temperature and annual precipitation). We thus conclude that pollination networks are highly dynamic and variable in composition of species and interactions among years. However, general patterns of network structure remain constant, indicating that species may be replaced by topologically similar species. These results suggest that pollination networks are to some extent robust against factors affecting species occurrences.