The structure of species interaction networks is important for species coexistence, community stability and exposure of species to extinctions. Two widespread structures in ecological networks are modularity, i.e. weakly connected subgroups of species that are internally highly interlinked, and nestedness, i.e. specialist species that interact with a subset of those species with which generalist species also interact. Modularity and nestedness are often interpreted as evolutionary ecological structures that may have relevance for community persistence and resilience against perturbations, such as climate-change. Therefore, historical climatic fluctuations could influence modularity and nestedness, but this possibility remains untested. This lack of research is in sharp contrast to the considerable efforts to disentangle the role of historical climate-change and contemporary climate on species distributions, richness and community composition patterns. Here, we use a global database of pollination networks to show that historical climate-change is at least as important as contemporary climate in shaping modularity and nestedness of pollination networks. Specifically, on the mainland we found a relatively strong negative association between Quaternary climate-change and modularity, whereas nestedness was most prominent in areas having experienced high Quaternary climate-change. On islands, Quaternary climate-change had weak effects on modularity and no effects on nestedness. Hence, for both modularity and nestedness, historical climate-change has left imprints on the network structure of mainland communities, but had comparably little effect on island communities. Our findings highlight a need to integrate historical climate fluctuations into eco-evolutionary hypotheses of network structures, such as modularity and nestedness, and then test these against empirical data. We propose that historical climate-change may have left imprints in the structural organisation of species interactions in an array of systems important for maintaining biological diversity.