The Mediterranean Basin is the region of Europe most vulnerable to negative climate-change impacts, including forest decline, increased wildfire, and biodiversity loss. Because humans have affected Mediterranean ecosystems for millennia, it is unclear whether the region's native ecosystems were more resilient to climate change than current ecosystems, and whether they would provide sustainable management options if restored. We simulated vegetation with the LANDCLIM model, using present-day climate as well as future climate-change scenarios, in three representative areas that encompass a broad range of Mediterranean conditions and vegetation types. Sedimentary pollen records that document now-extinct forests help to validate the simulations. Forests modeled under present climate closely resemble the extinct forests when human disturbance is limited; under future scenarios, characterized by increased temperatures and decreased precipitation, extinct forests are projected to re-emerge. When combined with modeling, paleoecological evidence reveals the potential of native vegetation to re-establish under current and future climate conditions, and provides a template for novel management strategies to maintain forest productivity and biodiversity in a warmer and drier future.