Few primary care physicians routinely counsel for exercise, despite the benefits of physical activity and the high prevalence of inactivity. The objective of this study is to assess the effectiveness of Physician-Based Assessment and Counseling for Exercise (PACE), a brief, behavior-based tool for primary care providers counseling healthy adults. This study is a randomized controlled trial of 812 patients age 30 years or older registered for well visits at 32 primary care physician offices at a staff model health maintenance organization. Intervention physicians were trained to deliver PACE exercise counseling protocols at the index visit, and one reminder telephone call occurred at 1 month. An enhanced intervention group received additional activity reminders. At the 6-month follow-up, the control group did not differ significantly from the intervention group for energy expended (2,048 kcal/week versus 2,108 kcal/ week, P = 0.77), time spent in walking or other moderate to vigorous activities (202 min/week versus 187 min/ week, P = 0.99), mental health, physical function, or behaviors previously shown to predict activity change. Among the intervention patients, the stages-of-change score for Contemplators increased significantly compared with controls (P = 0.03), but without a significant change in energy expended. Baseline levels of physical activity counseling were high (50%), as were baseline patient physical activity levels (61% exercised at least three times a week). These results suggest that a one-time PACE counseling session with minimal reinforcement, in a setting with high baseline levels of activity, does not further increase activity. The finding that Contemplators advanced in stage of behavior change suggests that further studies are needed to examine long-term, repeated counseling interventions.