Background: Evidence on the efficacy of smartphone applications (apps) for reducing body weight and other measurements of adiposity sustainably is not conclusive. Objective: To evaluate the effect of adding an app for 3 months to traditional counselling on physical activity (PA) and a heart-healthy diet for the modification of measurements of adiposity at 3 and 12 months after intervention. Methods: This randomised clinical trial included 833 subjects. The counselling and app group (IG) had 415 subjects, while 418 were included in the counselling only group (CG). The primary outcome was adiposity measurements at 3 and 12 months after intervention. The secondary outcome was the effect of the intervention by sex. Intervention: Counselling on a heart-healthy diet and PA was given to both groups. The IG also received training in the use of a smartphone app designed to promote a heart-healthy diet and PA, and this group was given access to this application for 3 months. Outcome measurements included waist circumference (WC), body mass index (BMI) and Clínica Universidad de Navarra – body adiposity estimator (CUN-BAE). Results: In the IG at 12 months, the following decreased: WC −0.72 cm (95% confidence interval [CI]: −2.35 to −0.02) and CUN-BAE −0.35 (95% CI: −0.63 to −0.06). These decreases were only observed in women. After baseline adjustment, the beneficial effect was maintained in the IG compared to the CG at 12 months in terms of WC (−0.67; 95% CI: −0.29 to −0.02) and CUN-BAE (−0.57; 95% CI: −1.10 to −0.04), but only in women. Conclusions: An intervention of nutritional counselling and PA plus the smartphone app with personalised recommendations compared to CG showed beneficial results in terms of reduction of abdominal obesity and the percentage of body fat in women, but not in men.