Background: Physical activity interventions targeting older adults are optimized if barriers and enablers are better understood. This study identified barriers and enablers of physical activity and examined whether these were associated with meeting physical activity recommendations. Methods: 2225 adults aged 65 years and above who perceived themselves to be insufficiently active but would like to be more physically active self-reported their barriers and enablers to physical activity in the 2009 New South Wales Falls Prevention Survey. Binary logistic regression analyses examined associations between barriers and enablers and meeting the physical activity recommendation. Results: After adjusting for gender, age, BMI, and education, people who listed ill health (52%; OR = 0.56, 95% CI 0.45 to 0.70) as a barrier or who listed people to exercise with (4%; OR = 0.49, 95% CI 0.27 to 0.88) as an enabler had significantly lower odds of meeting recommendations. Those citing too expensive (3%) as a barrier (OR = 2.07, 95% CI 1.11 to 3.87) or who listed nothing will help (29%; OR = 1.40, 95% CI 1.10 to 1.77) and making time to be active (9%; OR = 1.78, 95% CI 1.23 to 2.58) as enablers had significantly higher odds of meeting physical activity recommendations. Conclusions: These findings give insights into older adults' perceptions of factors that influence their physical activity, which could assist physical activity program planning in this population.