Climate change presents new challenges for selecting species for restoration. If migration fails to keep pace with climate change, as models predict, the most suitable sources for restoration may not occur locally at all. To address this issue we propose a strategy of “prestoration”: utilizing species in restoration for which a site represents suitable habitat now and into the future. Using the Colorado Plateau, USA as a case study, we assess the ability of grass species currently used regionally in restoration to persist into the future using projections of ecological niche models (or climate envelope models) across a suite of climate change scenarios. We then present a technique for identifying new species that best compensate for future losses of suitable habitat by current target species. We found that the current suite of species, selected by a group of experts, is predicted to perform reasonably well in the short-term, but that losses of prestorable habitat by mid-century would approach 40%. Using an algorithm to identify additional species, we found that fewer than ten species could compensate for nearly all of the losses incurred by the current target species. This case study highlights the utility of integrating ecological niche modeling and future climate forecasts to predict the utility of species in restoring under climate change across a wide range of spatial and temporal scales.