BACKGROUND: Interventions promoting physical activity by General Practitioners (GPs) lack a strong evidence base. Recruiting participants to trials in primary care is challenging. We investigated the feasibility of (i) delivering three interventions to promote physical activity in inactive participants and (ii) different methods of participant recruitment and randomised allocation. METHODS: We recruited general practices from Devon, Bristol and Coventry. We used a 2-by-2 factorial design for participant recruitment and randomisation. Recruitment strategies were either opportunistic (approaching patients attending their GP surgery) or systematic (selecting patients from practice lists and approaching them by letter). Randomisation strategies were either individual or by practice cluster. Feasibility outcomes included time taken to recruit the target number of participants within each practice. Participants were randomly allocated to one of three interventions: (i) written advice (control); (ii) brief GP advice (written advice plus GP advice on physical activity), and (iii) brief GP advice plus a pedometer to self-monitor physical activity during the trial. Participants allocated to written advice or brief advice each received a sealed pedometer to record their physical activity, and were instructed not to unseal the pedometer before the scheduled day of data collection. Participant level outcomes were reported descriptively and included the mean number of pedometer steps over a 7-day period, and European Quality of Life (EuroQoL)-5 dimensions (EQ-5D) scores, recorded at 12 weeks' follow-up. RESULTS: We recruited 24 practices (12 using each recruitment method; 18 randomising by cluster, 6 randomising by individual participant), encompassing 131 participants. Opportunistic recruitment was associated with less time to target recruitment compared with systematic (mean difference (days) -54.9, 95% confidence interval (CI) -103.6; -6.2) but with greater loss to follow up (28.8% versus. 6.9%; mean difference 21.9% (95% CI 9.6%; 34.1%)). There were differences in the socio-demographic characteristics of participants according to recruitment method. There was no clear pattern of change in participant level outcomes from baseline to 12 weeks across the three arms. CONCLUSIONS: Delivering and trialling GP-led interventions to promote physical activity is feasible, but trial design influences time to participant recruitment, participant withdrawal, and possibly, the socio-demographic characteristics of participants. TRIAL REGISTRATION NUMBER: ISRCTN73725618.