BACKGROUND: Over the last 10 years 'exercise referral schemes' have been popular even though the evidence for effectiveness of any one-to-one intervention in primary care is deficient. We report the results of a primary care based one-to-one intervention that compared the effect of two communication styles with a no-intervention control group on self-reported physical activity at 12 months. METHODS: In all, 1658 middle-aged men and women were randomly assigned to 30 minutes of brief negotiation or direct advice in primary care or a no-intervention control group. The main outcome was self-reported physical activity at 12 months. Secondary outcome measures included change in blood pressure and body mass index. RESULTS: Intention-to-treat analysis revealed no significant differences in physical activity between groups. Brief negotiation group participants who completed the study increased their physical activity significantly more than controls. There was no change in body mass index in any group. The brief negotiation group produced a greater reduction in diastolic blood pressure than direct advice. CONCLUSION: If patients whose health may benefit from increased physical activity seek advice in primary care, 20-30 minutes of brief negotiation to increase physical activity is probably more effective than similar attempts to persuade or coerce. However, blanket physical activity promotion in primary care is not effective. The most effective way of increasing physical activity in primary care has yet to be determined.