Objective. To examine the influence of fear of crime on walking for participants in a longitudinal study of residents in new suburbs. Methods. Participants (n = 485) in Perth, Australia, completed a questionnaire about three years after moving to their neighbourhood (2007-2008), and again four years later (2011-2012). Measures included fear of crime, neighbourhood perceptions and walking (min/week). Objective environmental measures were generated for each participant's neighbourhood, defined as the 1600 m road network distance from home, at each time-point. Linear regression models examined the impact of changes in fear of crime on changes in walking, with progressive adjustment for other changes in the built environment neighbourhood perceptions and demographics. Results. An increase in fear of crime was associated with a decrease in residents' walking inside the local neighbourhood. For each increase in fear of crime (i.e., one level on a five-point Likert scale) total walking decreased by 22 min/week (p = 0.002), recreational walking by 13 min/week (p = 0.031) and transport walking by 7 min/week (p = 0.064). Conclusion. This study provides longitudinal evidence that changes in residents' fear of crime influence their walking behaviours. Interventions that reduce fear of crime are likely to increase walking and produce public health gains.