Aging is accompanied by a progressive decline in muscle mass and an increase in fat mass, which are detrimental changes associated with the development of health conditions such as type-2 diabetes mellitus or chronic low-grade inflammation. Although both exercise as well as nutritional interventions are known to be beneficial in counteracting those age-related changes, data to which extent untrained elderly people may benefit is still sparse. Therefore, a randomized, controlled, 12-week interventional trial was conducted in which 134 healthy untrained participants (96 women and 38 men, age 59.4 ± 5.6 years, body mass index (BMI) 28.4 ± 5.8 kg/m2) were allocated to one of four study groups: (1) control group with no intervention (CON); (2) 2×/week aerobic and resistance training only (EX); (3) exercise routine combined with dietary counseling in accordance with the guidelines of the German Nutrition Society (EXDC); (4) exercise routine combined with intake of 2 g/day oil from Calanus finmarchicus (EXCO). Body composition (bioelectrical impedance analysis), as well as markers of glucose metabolism and blood lipids, were analyzed at the beginning and the end of the study. The highest decreases in body fat were observed within the EXCO group (−1.70 ± 2.45 kg, p < 0.001), and the EXDC (−1.41 ± 2.13 kg, p = 0.008) group. Markers of glucose metabolism and blood lipids remained unchanged in all groups. Taken together results of this pilot study suggest that a combination of moderate exercise and intake of oil from Calanus finmarchicus or a healthy diet may promote fat loss in elderly untrained overweight participants.