Background/Objectives <p>Due to the increasing prevalence of obesity, more effective methods are needed to support an individual’s eating behavior. We investigated the effects of a mobile health behavior change support system (mHBCSS) on eating behavior and the associations between changes in eating behavior and weight loss.</p> Methods <p>Altogether 200 volunteers (age 18–65 years, BMI 30–40 kg/m²) were enrolled in this study. Participants were randomized into two groups: group 1 with an immediate access to mHBCSS, or group 2 with a 6-month waiting period before mHBCSS. Three-Factor Eating Questionnaire-R18 and Binge Eating Scale were completed, and body weight was measured (0, 6, 12, and 18 months). The primary outcome was changes in cognitive restraint, uncontrolled eating, emotional eating, and binge eating.</p> Results <p>After 6 months, in group 1 with immediate access to mHBCSS cognitive restraint increased (8.4 scores, 95% CI: 4.1–12.8), while uncontrolled eating [−8.2 (−11.9 to −4.4)], emotional eating [−9.4 (−14.4 to −4.5)], and binge eating [−3.4 (−4.9 to −1.9)] decreased (all <i>p</i> &lt; 0.001). Also, weight loss in group 1 was associated with an increase in cognitive restraint (<i>p</i> = 0.015), and decreases in uncontrolled eating, emotional eating, and binge eating (all <i>p</i> &lt; 0.001) at the 6-month visit. No significant changes during the first 6 months were observed in group 2. Group 2 demonstrated the same changes in eating behavior after using the mHBCSS for 6 months. Significant eating behavior changes were maintained to the end of the follow-up in both groups. The retention rate was 98.5%, 89.0%, and 79.0% at the 6-, 12-, and 18-month visits.</p> Conclusion <p>The 6-month use of mHBCSS improved eating behavior, and changes in eating behavior were associated with weight loss. The stand-alone mobile application appears to be an effective method for changing eating behavior among people with obesity.</p>