Landscape optimization for biodiversity requires prediction of species distributions under alternative revegetation scenarios. We used Bayesian model averaging with logistic regression to predict probabilities of occurrence for 61 species of birds within highly fragmented box–ironbark forests of central Victoria, Australia. We used topographic, edaphic, and climatic variables as predictors so that the models could be applied to areas where vegetation has been cleared but may be replanted. Models were evaluated with newly acquired, independent data collected in large blocks of remnant native vegetation. Successful predictions were obtained for 18 of 45 woodland species (40%). Model averaging produced more accurate predictions than “single best” models. Models were most successful for smaller-bodied species that probably depend on particular vegetation types. Predictions for larger, generalist species, and seasonal migrants were less successful, partly because of changes in species distributions between model building (1995–1997) and validation (2004–2005) surveys. We used validated models to project occurrence probabilities for individual species across a 12,000-km2 region, assuming native vegetation was present. These predictions are intended to be used as inputs, along with landscape context and temporal dynamics, into optimization algorithms to prioritize revegetation. Longer-term data sets to accommodate temporal dynamics are needed to improve the predictive accuracy of models.