In conservation it is inevitable that surrogates be selected to represent the occurrence of hard-to-find species and find priority locations for management. However, species co-occurrence can vary over time. Here we demonstrate how temporal dynamics in species co-occurrence influence the ability of managers to choose the best surrogate species. We develop an efficient optimisation formulation that selects the optimal set of complementary surrogate species from any co-occurrence network. We apply it to two Australian datasets on successional bird responses to disturbances of revegetation and fire. We discover that a surprisingly small number of species are required to represent the majority of species co-occurrences at any one time. Because co-occurrence patterns are temporally dynamic, the optimal set of surrogates, and the number of surrogates required to achieve a desired surrogacy power, depend on sampling effort and the successional state of a system. Overlap in optimal sets of surrogates for representing 70% of co-occurring species ranges from zero to 57% depending on when the surrogacy decision is made. Surrogate sets representing early successional communities over-estimate the power of surrogacy decisions at later times. Our results show that in dynamic systems, optimal surrogates might be selected in different ways: 1) use short-term monitoring to choose a larger number of static less-informative surrogates; 2) use long-term monitoring to choose a smaller number of static high-power surrogates that may poorly represent early successional co-occurrence; 3) develop adaptive surrogate selection frameworks with high short-term and long-term surrogacy power that update surrogate sets and capture temporal dynamics in species co-occurrence. Our results suggest vigilance is needed when selecting surrogates for other co-occurring species in dynamic landscapes, as selected surrogates from one time may have reduced effectiveness at a different time. Ultimately, decisions that fail to acknowledge dynamic species co-occurrence will lead to uninformative or redundant surrogates.