Physical activity is associated with a decreased prevalence of obstructive sleep apnea and improved sleep efficiency. Studies on the effects of a comprehensive exercise program in a community setting remain limited. Our objective was to investigate the effects of a combined physical and oropharyngeal exercise program on the apnea-hypopnea index in patients with moderate to severe obstructive sleep apnea. This was a randomized clinical trial where the intervention group followed an eight-week urban-walking program, oropharyngeal exercises, and diet and sleep recommendations. The control group followed diet and sleep recommendations. A total of 33 patients were enrolled and randomized and, finally, 27 patients were included in the study (IG, 14; CG, 13) Obstructive sleep apnea patients were analyzed with a median age of 67 (52–74) and median apnea-hypopnea index of 32 events/h (25–41). The apnea-hypopnea index did not differ between groups pre- and post-intervention. However, in intervention patients younger than 60 (n = 6) a reduction of the apnea-hypopnea index from 29.5 (21.8–48.3) to 15.5 (11–34) events/h (p = 0.028) was observed. While a comprehensive multimodal program does not modify the apnea-hypopnea index, it could reduce body weight and increase the walking distance of patients with moderate to severe obstructive sleep apnea. Patients younger than 60 may also present a decreased apnea-hypopnea index after intervention.