Very brief interventions (VBIs) for physical activity are promising, but there is uncertainty about their potential effectiveness and cost. We assessed potential efficacy, feasibility, acceptability, and cost of three VBIs in primary care, in order to select the most promising intervention for evaluation in a subsequent large-scale RCT. Three hundred and ninety four adults aged 40-74 years were randomised to a Motivational (n = 83), Pedometer (n = 74), or Combined (n = 80) intervention, delivered immediately after a preventative health check in primary care, or control (Health Check only; n = 157). Potential efficacy was measured as the probability of a positive difference between an intervention arm and the control arm in mean physical activity, measured by accelerometry at 4weeks. For the primary outcome the estimated effect sizes (95% CI) relative to the Control arm for the Motivational, Pedometer and Combined arms were respectively: +20.3 (-45.0, +85.7), +23.5 (-51.3, +98.3), and -3.1 (-69.3, +63.1) counts per minute. There was a73% probability of a positive effect on physical activity for each of the Motivational and Pedometer VBIs relative to control, but only 46% for the Combined VBI. Only the Pedometer VBI was deliverable within 5min. All VBIs were acceptable and low cost. Based on the four criteria, the Pedometer VBI was selected for evaluation in a large-scale trial. Current Controlled Trials ISRCTN02863077 . Retrospectively registered 05/10/2012.