Background: Brief interventions (BIs) delivered in primary care have shown potential to increase physical activity levels and may be cost-effective, at least in the short-term, when compared with usual care. Nevertheless, there is limited evidence on their longer term costs and health benefits. Objectives: To estimate the cost-effectiveness of BIs to promote physical activity in primary care and to guide future research priorities using value of information analysis. Methods: A decision model was used to compare the cost-effectiveness of three classes of BIs that have been used, or could be used, to promote physical activity in primary care: 1) pedometer interventions, 2) advice/counseling on physical activity, and (3) action planning interventions. Published risk equations and data from the available literature or routine data sources were used to inform model parameters. Uncertainty was investigated with probabilistic sensitivity analysis, and value of information analysis was conducted to estimate the value of undertaking further research. Results: In the base-case, pedometer interventions yielded the highest expected net benefit at a willingness to pay of £20,000 per quality-adjusted life-year. There was, however, a great deal of decision uncertainty: the expected value of perfect information surrounding the decision problem for the National Health Service Health Check population was estimated at £1.85 billion. Conclusions: Our analysis suggests that the use of pedometer BIs is the most cost-effective strategy to promote physical activity in primary care, and that there is potential value in further research into the cost-effectiveness of brief (i.e., <30 minutes) and very brief (i.e., <5 minutes) pedometer interventions in this setting.