Background. This study examined associations between perceptions of the local neighborhood and walking and cycling among children. Methods. Children aged 5–6 years (n = 291) and 10–12 years (n = 919) were recruited from 19 Australian primary schools. Parents reported their child's usual walking or cycling to local destinations and their perceptions of their neighborhood. Ten- to twelve-year-olds were asked their perceptions of traffic, strangers, road safety and sporting venues, and their perceptions of their parent's views on these issues. Results. Five- to six-year-old boys whose parents believed there was heavy traffic in their area were 2.8 times more likely (95%CI = 1.1–6.8), and 5- to 6-year-old girls whose parents owned more than one car were 70% less likely (95%CI = 0.1–0.8), and whose parents believed that public transport was limited in their area were 60% less likely (95%CI = 0.2–0.9) than other children to walk or cycle at least three times per week. Parental belief that there were no lights or crossings was associated with walking or cycling among 10- to 12-year-old boys (OR = 0.4, 95%CI = 0.2–0.7). Among older girls, parent's belief that their child needed to cross several roads to reach play areas (OR = 0.4, 95%CI = 0.2–0.8) and that there is limited public transport in their area (OR = 0.7, 95%CI = 0.4–0.97), and child's belief that there were no parks or sports grounds near home (OR = 0.5, 95%CI = 0.3–0.8) were associated with a lower likelihood of walking or cycling. Conclusion. Perceptions of the local neighborhood may influence children's physical activity.