Background: Women living in socio-economically disadvantaged neighbourhoods are at increased risk for physical inactivity and associated health outcomes and are difficult to reach through personally tailored interventions. Targeting the built environment may be an effective strategy in this population subgroup. The aim of this study was to examine the mediating role of environmental perceptions in the relationship between the objective environment and walking for transportation/recreation among women from socio-economically disadvantaged neighbourhoods. Methods: Baseline data of the Resilience for Eating and Activity Despite Inequality (READI) study were used. In total, 4139 women (18–46 years) completed a postal survey assessing physical environmental perceptions (aesthetics, neighbourhood physical activity environment, personal safety, neighbourhood social cohesion), physical activity, and socio-demographics. Objectively-assessed data on street connectivity and density of destinations were collected using a Geographic Information System database and based on the objective z-scores, an objective destinations/connectivity score was calculated. This index was positively scored, with higher scores representing a more favourable environment. Two-level mixed models regression analyses were conducted and the MacKinnon product-of-coefficients test was used to examine the mediating effects. Results: The destinations/connectivity score was positively associated with transport-related walking. The perceived physical activity environment mediated 6.1% of this positive association. The destinations/connectivity score was negatively associated with leisure-time walking. Negative perceptions of aesthetics, personal safety and social cohesion of the neighbourhood jointly mediated 24.1% of this negative association. Conclusion: For women living in socio-economically disadvantaged neighbourhoods, environmental perceptions were important mediators of the relationship between the objective built environment and walking. To increase both transport-related and leisure-time walking, it is necessary to improve both objective walkability-related characteristics (street connectivity and proximity of destinations), and perceptions of personal safety, favourable aesthetics and neighbourhood social cohesion.