To compare the effects of a pedometer-based behavioral intervention (Fitness for Life [FFL] program) and a traditional high-intensity fitness (TRAD) program on physical activity (PA), Army Physical Fitness Test (APFT), and coronary heart disease risk factors in Army National Guard members who failed the APFT 2-mile run. From a pool of 261 Army National Guard, a total of 156 were randomized to TRAD or FFL for 24 weeks consisting of a 12-week progressive conditioning program followed by 12 weeks of maintenance. For both groups, the total APFT score and 2-mile run time/score improved from baseline to 12 weeks (FFL: down 7.4%, p = 0.03; TRAD: down 5%, p = 0.08) but at 24 weeks they had regressed toward baseline. PA improved modestly and coronary risk profile changed minimally in both groups. A pedometer-based exercise intervention had results similar to a high-intensity program for improving PA, APFT, and 2-mile run times/score. Neither group sustained the improved run times over the 12 weeks of maintenance.