Designing connected landscapes is among the most widespread strategies for achieving biodiversity conservation targets. The challenge lies in simultaneously satisfying the connectivity needs of multiple species at multiple spatial scales under uncertain climate and land-use change. To evaluate the contribution of remnant habitat fragments to the connectivity of regional habitat networks, we developed a method to integrate uncertainty in climate and land-use change projections with the latest developments in network-connectivity research and spatial, multipurpose conservation prioritization. We used land-use change simulations to explore robustness of species' habitat networks to alternative development scenarios. We applied our method to 14 vertebrate focal species of periurban Montreal, Canada. Accounting for connectivity in spatial prioritization strongly modified conservation priorities and the modified priorities were robust to uncertain climate change. Setting conservation priorities based on habitat quality and connectivity maintained a large proportion of the region's connectivity, despite anticipated habitat loss due to climate and land-use change. The application of connectivity criteria alongside habitat-quality criteria for protected-area design was efficient with respect to the amount of area that needs protection and did not necessarily amplify trade-offs among conservation criteria. Our approach and results are being applied in and around Montreal and are well suited to the design of ecological networks and green infrastructure for the conservation of biodiversity and ecosystem services in other regions, in particular regions around large cities, where connectivity is critically low.