An intervention trial with regular physical activity was carried out to test the hypothesis that walking speed is related to the level of cardiovascular fitness (maximal oxygen uptake). Earlier research has demonstrated that when VO2 max is held constant in a multiple regression analysis the association between walking speed and age (29–65 y) is eliminated. To describe the association between self-selected speeds of walking, and level of cardiovascular fitness, 63 men age 60 to 65 were studied before and after a 1 year program of exercise training. VO2 max was determined on a motor driven treadmill. A test of self-selected walking pace was administered over a 240 m indoor course. The men were asked to walk at 3 paces considered by the subjects to be rather slow, normal, and fast, respectively. They were randomly assigned with stratification for white and blue collar occupation to a program of exercise training (n = 33) or control (n = 27). The training program consisted of walking or jogging for 30 min three times per week for one year. After the training program the exercise group increased their VO2 max (9.5%) and their normal walking speed (1.29 to 1.43 m.s−1) significantly compared to the controls. A program of exercise endurance training will result in an increase in the speed of self-selected pace.