Networks of sites of high importance for conservation of biological diversity are a cornerstone of current conservation strategies but are fixed in space and time. As climate change progresses, substantial shifts in species' ranges may transform the ecological community that can be supported at a given site. Thus, some species in an existing network may not be protected in the future or may be protected only if they can move to sites that in future provide suitable conditions. We developed an approach to determine appropriate climate-change adaptation strategies for individual sites within a network that was based on projections of future changes in the relative proportions of emigrants (species for which a site becomes climatically unsuitable), colonists (species for which a site becomes climatically suitable), and persistent species (species able to remain within a site despite the climatic change). Our approach also identifies key regions where additions to a network could enhance its future effectiveness. Using the sub-Saharan African Important Bird Area (IBA) network as a case study, we found that appropriate conservation strategies for individual sites varied widely across sub-Saharan Africa, and key regions where new sites could help increase network robustness varied in space and time. Although these results highlight the potential difficulties within any planning framework that seeks to address climate-change adaptation needs, they demonstrate that such planning frameworks are necessary, if current conservation strategies are to be adapted effectively, and feasible, if applied judiciously.