Stages of Change were assessed for three stage definitions and two modes of health-enhancing physical activity (HEPA) in a representative telephone survey in Switzerland (participation 55.8%; n = 1471). Two five-stage definitions focusing either on intention to change or current behavior were integrated into a seven-stage concept, taking into account both aspects. The two target behaviors were activities with at least moderate intensity and activities with vigorous intensity. According to the two five-stage definitions, at least half of the participants were either in precontemplation (focus on intention) or in preparation (focus on behavior). Upon classification into the seven stages these large stage groups were differentiated. There were differences in the pros for change between the new stages of the seven-stage concept. One in seven participants was regularly active according to the moderate criteria, but not using the vigorous criteria, and one in every eight participants reported the inverse. Results show that an individual can be in different Stages of Change depending on the stage definition and be regularly active or not depending on the target behavior. The practical implications of the seven-stage algorithm and a two-dimensional matrix to classify participants for both moderate and vigorous intensity activities in an Internet-based HEPA program are presented.