Telomere length (TL) has been associated with aging and is determined by lifestyle. However, the mechanisms by which a dietary pattern such as the Mediterranean diet (MedDiet) affects TL homeostasis are still unknown. Our aim was to analyse the effect of an energy-restricted MedDiet with physical activity promotion (intervention group) versus an unrestricted-caloric MedDiet with no weight-loss advice (control group) on TL and 8-hydroxydeoxyguanosine (8-OHdG) plasma levels. In total, 80 non-diabetic participants with metabolic syndrome were randomly selected from the PREDIMED (PREvención con DIeta MEDiterránea)-Plus-Reus study. TL was measured by a hybridisation method and 8-OHdG levels by ELISA at baseline and after one year of intervention. Linear mixed models (LMM)—raw and after adjusting for potential confounders—were used to examine the associations between TL or 8-OHdG plasma levels by intervention group and/or time. A total of 69 subjects with available DNA samples were included in the analyses. A significant β-coefficient was found for time towards increasing values through the year of follow-up for TL (unadjusted β of 0.740 (95% CI: 0.529 to 0.951), and multivariable model β of 0.700 (95% CI: 0.477 to 0.922)). No significant βs were found, neither for the intervention group nor for the interaction between the intervention group and time. Regarding 8-OHdG plasma levels, no significant βs were found for the intervention group, time, and its interaction. Our results suggest that MedDiet could have an important role in preventing telomere shortening, but calorie restriction and exercise promotion did not provide an additional advantage concerning telomere length after one year of MedDiet intervention.