There is limited evidence on the causality of previously observed associations between neighborhood characteristics and physical activity (PA). We aimed to assess whether individual-level PA was associated with changes in fear of crime, social cohesion, green spaces, parking facilities, social disorder, and physical disorder that occurred over the past 3 years. In general, in neighborhoods where residents had more favorable perceptions of the environment in 2006, residents were more likely to be physically active in 2009. In addition, improvements between 2006 and 2009 with respect to perceived social cohesion, green spaces, social disorder, and physical disorder were associated with increased odds of being active in 2009. For both the levels in 2006 and trends in the period 2006–2009, the associations were somewhat stronger among women than among men, but associations did not vary by age or length of residence. For several environmental factors, we observed that not only the levels at a certain point in time, but also recent improvements over time were related to PA. These results provide new support for a causal relationship between these environmental factors and PA.