These days, mobile phone dependency (MPD) has become one of the most imperative and impressive puzzles in the area of behavioral addictions and public health across the world, especially the individuals with MPD that might frequently crave using mobile phones themselves. The target of the current study was to determine whether moderate-intensity aerobic exercise could reduce the craving degree for mobile phones for university students with MPD by a randomized, controlled trial. Sixty Chinese undergraduates, including 30 male and 30 female students aged from 18 to 22 years (20.08 ± 1.94 years) with MPD were recruited and then randomly assigned to the exercise group (n = 30) or the control group (n = 30) with even numbers by gender and major. Participants in the exercise group were required to perform an acute moderate-intensity treadmill exercise lasting for 30 min at 45−68% heart rate reserve (HRR) with background music, while the control group were only asked to listen to the same music for 40 min without any exercise. Sport watches were employed to monitor their heart rate (HR), and the exercise group was also obliged to report their rating of perceived exertion (RPE). After completing the experimental task, a visual analog scale (VAS) was used to evaluate their craving degree for mobile phones, and an independent samples t-test was computed to reveal the difference in the scores of craving degree for mobile phones between the two groups. The results showed that the VAS score for the exercise group (3.77 ± 1.36) was significantly lower (p < 0.001) than that of the control group (6.11 ± 1.39). The findings suggested that acute moderate-intensity aerobic exercise could be an effective and reliable means to help deal with the issue of mobile phones craving for the undergraduates with MPD, and more longitudinal intervention studies and control trial designs should be conducted in the near future to further test the long-term effects of this exercise.