Telomere shortening may cause genome instability and is an initiating event in colorectal cancer (CRC). Obesity is associated with reduced telomere length in lymphocytes and is a risk factor for CRC, but the impact of obesity on telomere length in the rectal mucosa is unknown. The purpose of this study was to investigate the effect of weight loss, induced by calorie-restricted diets, on telomere length in the rectal mucosa of obese men. Midrectal biopsies were collected by sigmoidoscopy at three time points (at weeks 0, 12, and 52) during a programmed weight loss intervention. Weight was reduced by an average of 10.6 kg across the study. Telomere length, measured by quantitative real-time PCR (qPCR), was negatively correlated with body mass index (BMI) (r = -0.13, p = 0.05) at baseline (n = 54) and increased at week 12 (four-fold increase) and week 52 (10-fold increase) (analysis of covariance [ANCOVA] p = 0.01, n = 12). Abasic sites in DNA decreased at week 12 (30% decrease) and week 52 (65% decrease) (analysis of variance [ANOVA] p = 0.02). Furthermore, gain of telomere length appeared to be greater if more weight and body fat was lost (r = -0.65, p = 0.01 and r = -0.56, p = 0.01, respectively). These results suggest that weight loss by caloric-restricted diets may contribute to the prevention of telomere shortening and DNA base damage, which are important initiating events in carcinogenesis.