Restoration of native vegetation is required in many regions of the world, but determining priority locations for revegetation is a complex problem. We consider the problem of determining spatial and temporal priorities for revegetation to maximize habitat for 62 bird species within a heavily cleared agricultural region, 11000 km2 in area. We show how a reserve-selection framework can be applied to a complex, large-scale restoration-planning problem to account for multi-species objectives and connectivity requirements at a spatial extent and resolution relevant to management. Our approach explicitly accounts for time lags in planting and development of habitat resources, which is intended to avoid future population bottlenecks caused by delayed provision of critical resources, such as tree hollows. We coupled species-specific models of expected habitat quality and fragmentation effects with the dynamics of habitat suitability following replanting to produce species-specific maps for future times. Spatial priorities for restoration were determined by ranking locations (150-m grid cells) by their expected contribution to species habitat through time using the conservation planning tool, "Zonation." We evaluated solutions by calculating expected trajectories of habitat availability for each species. We produced a spatially explicit revegetation schedule for the region that resulted in a balanced increase in habitat for all species. Priority areas for revegetation generally were clustered around existing vegetation, although not always. Areas on richer soils and with high rainfall were more highly ranked, reflecting their potential to support high-quality habitats that have been disproportionately cleared for agriculture. Accounting for delayed development of habitat resources altered the rank-order of locations in the derived revegetation plan and led to improved expected outcomes for fragmentation-sensitive species. This work demonstrates the potential for systematic restoration planning at large scales that accounts for multiple objectives, which is urgently needed by land and natural resource managers.