Background: Women are less physically active, report greater perceived barriers for exercise, and show higher levels of depressive symptoms. This contributes to high global disability. The relationship between perceived barriers for physical activity and depressive symptoms in women remains largely unexplored. The aims of this cross-sectional analysis were to examine the association between physical activity barriers and depressive symptoms, and identify types of barriers in physically inactive community-dwelling women. Methods: Three hundred eighteen physically inactive women aged 25–65 years completed the Barriers to Being Active Quiz (BBAQ) developed by the Centers for Disease Control and Prevention, and the Center for Epidemiological Studies Depression Scale at the baseline visit of the mobile phone-based physical activity education trial. The BBAQ consists of six subscales (lack of time, social influence, lack of energy, lack of willpower, fear of injury, lack of skill, and lack of resources). We used multivariate regression analyses, correcting for sociodemographics. Results: Higher physical activity barriers were associated with greater depressive symptoms scores (linear effect, estimate = 0.75, 95% confidence interval [CI]: 0.39–1.12, p < 0.001). This effect appeared to taper off for the higher barrier scores (quadratic effect, estimate: -0.02, 95% CI: -0.03 to -0.01, p = 0.002). Exploratory analyses indicated that these associations were most driven by the social influence (p = 0.027) and lack of energy subscales (p = 0.017). Conclusions: Higher depression scores were associated with higher physical activity barriers. Social influence and lack of energy were particularly important barriers. Addressing these barriers may improve the efficacy of physical activity interventions in women with higher depressive symptoms. Future research should assess this in a randomized controlled trial.