Obesity is endemic in human populations in the western society, and with mounting evidence that the intestinal ecological environment plays a major role in its pathogenesis, identification of therapies based on intestinal microbiota modulation are gaining attention. Obesity in companion animals is also a common clinical problem. We set out using a multidimensional approach, to determine the effectiveness and safety of a weight loss program for horses incorporating diet restriction and exercise. In addition, we aimed to investigate the effect of this program on the overall intestinal health of overweight sedentary horses. The investigation comprised of a randomized, controlled, 6-week study of 14 overweight sedentary horses and ponies who were blocked for age, gender, and breed (controls n = 7, treatment n = 7). The treatment group were fed a restricted diet (1.4% of body weight dry matter intake) and the control group a maintenance diet (2% of body weight as dry matter intake) over the study period. The treatment group were subjected to a prescribed exercise regime, while the control group were exercised to mimic foraging conditions. Several clinical measurements were taken at the start and end of the study, including morphological parameters, ultrasound measurements of subcutaneous fat, and blood pressure. Fecal microbiota analysis was performed using 16S rRNA gene sequence analysis, and fecal metabolome was analyzed using NMR spectroscopy, on samples taken at weeks 1, 3, and 6 of the study. All horses completed the study period successfully. However, two of the treatment group had to have modified exercise regimes. The treatment group showed significant weight loss (p < 0.00001) and an associated decrease in waste circumference (p < 0.0001) when compared with the control group. The alpha-diversity of the fecal microbiota in the treatment group showed a significant increase from the start to the end of the study period (p < 0.05); however, there was no significant difference between groups at any sampling point. There were significant changes (p < 0.05) in the metabolome in both groups between the start and end of the study, but not between groups at any sampling point. Finally, the resting blood pressure of all horses was significantly lower by the end of the study.