Positive influences of natural and built environment characteristics on human physical activity have been observed mainly in high-income countries, but mixed results exist. We explored these relationships in Rio de Janeiro, Brazil, where exuberant nature coexists with high levels of social inequality and urban violence. Data originated from questionnaires self-administered by 1731 civil servants at university campuses who participated in 4 waves (1999, 2001, 2007, 2012) of a longitudinal study, and had their residential addresses geocoded. In multinomial regression models, adjusted for individual sociodemographic characteristics, mutually adjusted associations were estimated between 13-year trajectories of non-work physical activity and 8 contextual variables: distances from waterfronts, cycle paths, outdoor gym equipment, and squares; 2 indicators of exposure to greenness (a vegetation index - NDVI - derived from satellite images, and trees close to home); an indicator of walkability (street density), and neighborhood average income. Compared to participants living in the upper quartile of distance to waterfronts, those living in its lowest quartile had 2.6-fold higher odds (aOR: 2.62, 95% CI: 1.37–5.01) of reporting non-work PA in all 4 study waves. Similar results were observed in relation to distance to cycle paths; no independent associations were observed with other natural and built environment variables.