Aim Several large-mammal species in Europe have recovered and recolonized parts of their historical ranges. Knowing where suitable habitat exists, and thus where range expansions are possible, is important for proactively promoting coexistence between people and large mammals in shared landscapes. We aimed to assess the opportunities and limitations for range expansions of Europe's two largest herbivores, the European bison (Bison bonasus) and moose (Alces alces). Location Central Europe. Methods We used large occurrence datasets from multiple populations and species distribution models to map environmentally suitable habitats for European bison and moose across Central Europe, and to assess human pressure inside the potential habitat. We then used circuit theory modeling to identify potential recolonization corridors. Results We found widespread suitable habitats for both European bison (>120,000 km2) and moose (>244,000 km2), suggesting substantial potential for range expansions. However, much habitat was associated with high human pressure (37% and 43% for European bison and moose, respectively), particularly in the west of Central Europe. We identified a strong east–west gradient of decreasing connectivity, with major barriers likely limiting natural recolonization in many areas. Main conclusions We identify major potential for restoring large herbivores and their functional roles in Europe's landscapes. However, we also highlight considerable challenges for conservation planning and wildlife management, including areas where recolonization likely leads to human–wildlife conflict and where barriers to movement prevent natural range expansion. Conservation measures restoring broad-scale connectivity are needed in order to allow European bison and moose to recolonize their historical ranges. Finally, our analyses and maps indicate suitable but isolated habitat patches that are unlikely to be colonized but are candidate locations for reintroductions to establish reservoir populations. More generally, our work emphasizes that transboundary cooperation is needed for restoring large herbivores and their ecological roles, and to foster coexistence with people in Europe's landscapes.