Abstract Background Counseling in combination with pedometer use has proven to be effective in increasing physical activity and improving health outcomes. We investigated the cost-effectiveness of this intervention targeted at one million insufficiently active adults who visit their general practitioner in the Netherlands. Methods We used the RIVM chronic disease model to estimate the long-term effects of increased physical activity on the future health care costs and quality adjusted life years (QALY) gained, from a health care perspective. Results The intervention resulted in almost 6000 people shifting to more favorable physical-activity levels, and in 5100 life years and 6100 QALYs gained, at an additional total cost of EUR 67.6 million. The incremental cost-effectiveness ratio (ICER) was EUR 13,200 per life year gained and EUR 11,100 per QALY gained. The intervention has a probability of 0.66 to be cost-effective if a QALY gained is valued at the Dutch informal threshold for cost-effectiveness of preventive intervention of EUR 20,000. A sensitivity analysis showed substantial uncertainty of ICER values. Conclusion Counseling in combination with pedometer use aiming to increase physical activity may be a cost-effective intervention. However, the intervention only yields relatively small health benefits in the Netherlands.