The Natura 2000 network is the centerpiece of European nature conservation policy but its effectiveness is challenged by ongoing landscape change. Our objective was to assess landscape connectivity between Natura 2000 sites in the biodiversity-rich western Mediterranean region. We used the wood mouse as a focal species with short-range dispersal and obtained genetic data for 393 individuals uniformly distributed between two Natura 2000 sites in SW Portugal. We created a map of connectivity between the two sites that was based on a stack of analyses including reciprocal causal modeling and least-cost path modeling coupled with resistant kernel analysis. Wood mice in the study area were genetically diverse and connected by gene flow over a large area. We did not find evidence of major population subdivision in the study area. Gene flow was limited by geographic distance, with significant genetic similarity between individuals within 3 km of each other. Vegetation cover and land use explained more of the variation in genetic distance than geographic distance alone. In particular, agroforestry areas and transitional woodland were associated with higher costs to movement than forest or arable land uses. This result may have been influenced by the difficulty in classifying land use in the open montado. The Natura 2000 sites we studied are well connected by multiple corridors for dispersal. Our analysis also highlighted the importance of the Serra de Grândola, part of the European Long Term Ecological Research Network but not yet included in Natura 2000.