Current countermeasures to space flight related physiological deconditioning have not been sufficiently effective. We believe that a comprehensive countermeasure is the combination of intermittent centrifugation (artificial gravity) and exercise. We aim to test the long-term effectiveness of this combination in terms of fitness benefits. As a first-order determination of effectiveness, subjects participated in an eight-week exercise program. Three times per week, they exercised using a stair-stepper on a short-radius (2 m) centrifuge spinning at 30 RPM, maintaining a target heart rate that was systematically increased over the exercise period. During the sessions, foot forces and stepping cadence, heart rate, and perceived exertion were measured. Before and after the eight-week exercise program, measurements included: body fat percentage, bone mineral content, quadriceps extension strength, push-ups endurance, stepping cadence for a given heart rate, and maximum stepping endurance. We find that stair-stepping on a centrifuge is safe and comfortable. Preliminary fitness results indicate that stair-stepping on a centrifuge may be effective in improving aerobic fitness, body composition, and strength. These results indicate that such a combination may also be effective as a countermeasure to space flight deconditioning.