BACKGROUND: Physical activity is a major modifiable risk factor for cardiovascular disease, but it is unclear what combination of feasible approaches, using existing resources in primary care, work best to initiate increased physical activity. AIM: To assess three approaches to initiate increased physical activity. DESIGN OF STUDY: Randomised controlled (2 X 2 X 2) factorial trial. SETTING: Four general practices. METHOD: One hundred and fifty-one sedentary patients with computer documented risk factors for cardiovascular disease were randomised to eight groups defined by three factors: prescription by general practitioners (GPs) for brisk exercise not requiring a leisure facility (for example, walking) 30 minutes per day, 5 days per week; counselling by practice nurses, based on psychological theory to modify intentions and perceived control of behaviour, and using behavioural implementation techniques (for example, contracting, 'rehearsal'); use of the Health Education Authority booklet 'Getting active, feeling fit'. RESULTS: Single interventions had modest effects. There was a trend from the least intensive interventions (control +/- booklet) to the more intensive interventions (prescription and counselling combined +/- booklet) for both increased physical activity and fitness (test for trend, P = 0.02 and P = 0.05, respectively). Only with the most intense intervention (prescription and counselling combined) were there significant increases in both physical activity and fitness from baseline (Godin score = 14.4, 95% confidence interval [CI] = 7.8 to 21, which was equivalent to three 15-minute sessions of brisk exercise and a 6-minute walking distance = 28.5 m, respectively, 95% CI = 11.1 to 45.8). Counselling only made a difference among those individuals with lower intention at baseline. CONCLUSION: Feasible interventions using available staff, which combine exercise prescription and counselling explicitly based on psychological theory, can probably initiate important increases in physical activity.