From a mobility perspective, walking is considered to be the most sustainable transport mode. One of the consequences of motor-oriented urban configuration on pedestrian mobility is urban fragmentation, which affects sustainability in cities. In this paper, we use a natural-based approach to landscape fragmentation and connectivity (inherited from landscape ecology) for pedestrian mobility planning. Our aim is to design a useful methodology to identify priority pedestrian corridors, and to assess the effects of implementing barrier-free pedestrian corridors in the city. For this purpose, we developed a method that integrates Geographical Information Systems (GIS) network analysis with kernel density methods, which are commonly used for designating habitat corridors. It was applied to Vitoria-Gasteiz (Spain). Pedestrian mobility was assessed by comparison of travel times between different scenarios. Results show that the implementation of pedestrian corridors reduces travel time by approximately 6%. Thus, an intervention in a small percentage of the city’s street network could considerably reduce pedestrian travel times. The proposed methodology is a useful tool for urban and transport planners to improve pedestrian mobility and manage motorised traffic.