Considering that the prevalence of overweight and obesity in Southeast of Spain is high, the aim of this work was to analyze the relation between the adherence to a personalized diet and the effectiveness of changes in the body composition in overweight and obese adults in this region. This quasi-experimental study presents the following selection criteria: attendance at the consultation between 2006 and 2012, subjects ≥ 19 years of age with overweight or obesity. In total, 591 overweight or obese individuals were involved in this study, attending 4091 clinic consultations in total. Most of the sample consisted of subjects who attended >3 consultations (>1.5 months), and were females aged 19–64 years who obtained clinically significant changes in fat mass (FM, ≥5%) and recommended changes in fat-free mass (FFM, ≥0%). Based on the results obtained and the experience gained from this research, the following recommendations are established: (i) record fat mass and fat-free mass index as a complement to body mass index; (ii) use FM and FFM to evaluate effectiveness of interventions with the aim of obtaining body composition changes; (iii) use personalized diet to achieve significant changes in FM and avoid non-recommended changes in FFM.