There is strong evidence that considerable health benefits can be achieved even with small amounts of physical activity. However, getting people to exercise regularly is a major challenge not least in the elderly population. This study investigated the feasibility and physiological health effects of a pragmatic 15-week exercise programme for sedentary elderly. In a single-blind randomised controlled trial, 45 sedentary 60-83-year-olds (25 women, 20 men) were randomly assigned (2:1 ratio) to a training group (TG, n=30) or a control group (CG, n=15). The training in TG consisted of a combination of exercise modalities (i.e., strength, aerobic fitness, stability, and flexibility training) performed once a week as supervised group-based training and a weekly home-based training for 15 weeks. Feasibility outcomes were exercise intensity, adherence, and adverse events. The primary outcome was change in aerobic fitness (VO2max/kg). Adherence was high (81%) for the supervised exercise and low (0%) for the home-based exercise. No acute injuries occurred in TG, but 4 subjects (13%) reported considerable joint pain related to training. Average heart rate (HR) during the supervised training was 104±12 beats/min (69.3±8.0%HRmax), with 3.9±7.3% of training time >90%HRmax. Intention-to-treat analyses revealed no between-group differences for aerobic fitness (P=0.790) or any secondary cardiovascular outcomes at 15-week follow-up (resting HR or blood pressure; P>0.05). Compared to CG, bodyweight (-2.3 kg, 95% CI -4.0 to -7.0; P=0.006), total fat mass (-2.0 kg, 95% CI -3.5 to -0.5; P=0.01), and total fat percentage (-1.6%, 95% CI -2.8 to -0.3; P=0.01) decreased in TG. The group-based supervised training had high adherence and moderate exercise intensity, whereas the home-based training was not feasible in this study population. This exercise programme performed once a week did not improve aerobic fitness. Thus, supervised training with more vigorous intensity control appears advisable. Clinical Study registration number is H-15016951.