Summary 1. Attempts to restore damaged ecosystems usually emphasize structural aspects of biodiversity, such as species richness and abundance. An alternative is to emphasize functional aspects, such as patterns of interaction between species. Pollination is a ubiquitous interaction between plants and animals. Patterns in plant-pollinator interactions can be analyzed with a food web or complex-systems approach and comparing pollination webs between restored and reference sites can be used to test whether ecological restoration has taken place. 2. Using an ecological network approach, we compared plant-pollinator interactions on four pairs of restored and ancient heathlands 11 and 14 years following initiation of restoration management. We used the network data to test whether visitation by pollinators had been restored and we calculated pollinator importance indices for each insect species on the eight sites. Finally, we compared the robustness of the restored and ancient networks to species loss. 3. Plant and pollinator communities were established successfully on the restored sites. There was little evidence of movement of pollinators from ancient sites onto adjacent restored sites, although paired sites correlated in pollinator species richness in both years. There was little insect species overlap within each heathland between 2001 and 2004. 4. A few widespread insect species dominated the communities and were the main pollinators. The most important pollinators were typically honeybees (Apis mellifera), species of bumblebee (Bombus spp.), and one hoverfly species (Episyrphus balteatus). The interaction networks were significantly less complex on restored heathlands, in terms of connectance values, although in 2004 the low values might reflect the negative relationship between connectance and species richness. Finally, there was a trend of restored networks being more susceptible to perturbation than ancient networks, although this needs to be interpreted with caution. 5. Synthesis and applications. Ecological networks provide a powerful tool for assessing the outcome of restoration programs. Our results indicate that heathland restoration does not have to occur immediately adjacent to ancient heathland for functional pollinator communities to be established. Moreover, in terms of restoring pollinator interactions, heathland managers need only be concerned with the most common insect species. Our focus on pollination demonstrates how a key ecological service can serve as a yardstick for judging restoration success.