To create neighbourhood environments that encourage physical activity, it is important to know which neighbourhood characteristics are most influential. We examined the association of neighbourhood safety with leisure-time walking and cycling in the population at large, as well as in some subgroups in terms of sex, age, ethnicity and socio-economic position. We used data of 19,914 participants (18–70 years) from a study in Amsterdam, the Netherlands. Leisure-time walking and cycling in minutes/week were assessed with standard questionnaire. Geographic Information System techniques were used to examine neighbourhood safety (range = 1–10). Multilevel linear regression analyses showed positive associations between safety and walking (B = 7.9, 95% CI = −6.2–21.9) and cycling (B = 14.8, 95% CI = 2.5–27.1), but only the association with cycling was statistically significant. Higher safety levels were significantly associated with more cycling in women and individuals of Turkish and Moroccan origin. Stronger evidence is needed to inform policies to stimulate walking and cycling by improving neighbourhood safety.