Objectives: In this study, we identify physical activity (PA) benefits and barriers and changes in response to a 12-week interactive voice response (IVR)-supported PA telephone counseling intervention. Methods: Participants (N = 63) completed the Exercise Benefits/Barriers Scale (EBBS) at baseline and post-intervention. Exit interview responses to benefits and barriers items were analyzed qualitatively. Results: High exercise benefits and moderate barriers were reported at baseline. The intervention arm experienced a statistically significant greater improvement in barriers (but not benefits) from baseline to week 12, compared to the control arm. These relationships held when we controlled for sex, age, ethnicity, baseline PA, baseline barriers, and baseline benefits. Themes from interviews corroborated the lack of change in PA benefits and decreases in PA barriers and emphasized that support and accountability helped address barriers related to time and motivation. Conclusions: IVR-supported interventions show promise for improving perceived exercise barriers and possibly exercise benefits.