Background: Encouraging cycling could increase levels of physical activity and health in the community. A population survey of cycling and physical activity was conducted as part of the baseline evaluation of a new intervention research project (Cycling Connecting Communities). Methods: A telephone survey of adults (18+) living within 2 kilometers of selected major new bicycle paths in 3 local government areas in south western Sydney, Australia was conducted using a 2-stage sampling method. Multiple logistic regression analyses examined factors associated with riding in the last year, wanting to cycle more, and use of local bicycle paths. Results: With a 65% response rate, 1450 interviews were completed. Having ridden a bicycle in the past year was associated with younger age, being male, having access to a bicycle, and living close to destinations of interest. Two thirds of respondents (65%) wanted to ride more than they currently did. Factors associated with wanting to ride more were having children aged between 5–18 years, having used local bicycle paths, and perceptions of ease of cycling. Conclusions: The study found that there is a latent desire for more cycling among respondents, prompted to some extent by having children of an age (5–18 years) that like cycling, and having a reasonable opportunity to cycle due to local bicycle paths. Being relatively close to destinations of interest increases the likelihood of recent cycling.