Background: The effectiveness of low-carbohydrate diets (LCDs) on weight loss and exercise for improving cardiometabolic fitness have been well documented in the literature, but the effects of LCDs and whether adding exercise to a LCD regime could additionally benefit mental health (e. g., by lowering the level of anxiety) and associated changes in eating behavior are less clear in overweight and obese populations. Therefore, this study aimed to investigate the effects of a 4-week LCD with or without exercise on anxiety and eating behavior, and to explore the associations between changes in the psychological state and physiological parameters (i.e., body composition, aerobic fitness, blood pressure, lipid profile, and metabolic hormones). Methods: Seventy-four overweight Chinese women [age: 20.8 ± 3.0 years, body mass index (BMI): 25.3 ± 3.3 kg·m] completed the 4-week randomized controlled trial, which included a LCD group (i.e., ~50 g daily carbohydrate intake) with exercise training 5 days/week (LC-EXE, n = 26), a LCD group without exercise training (LC-CON, n = 25) and a control group that did not modify their habitual diets and physical activity (CON, n = 23). Levels of anxiety, eating behavior scores and physiological parameters (i.e., body weight, V̇O, blood pressure, fasting glucose, blood lipids, and serum metabolic hormones including insulin, C-peptide, leptin, and ghrelin) were measured before and after the intervention. Results: There were significant reductions in anxiety levels in the LC-EXE compared with the LC-CON group, while no statistical changes were found in eating behaviors in any conditions after the 4-week intervention. Significant reduction in weight (~3.0 kg or 4%, p < 0.01) and decreases in insulin (~30% p < 0.01), C-peptide (~20% p < 0.01), and leptin (~40%, p < 0.01) were found in both LC-CON and LC-EXE groups, but adding exercise to a LCD regime generated no additional effects. There were significant improvements in V̇O (~15% p < 0.01) and anxiety (~25% p < 0.01) in the LC-EXE compared with the LC-CON group, while no statistical differences were found between CON and LC-CON treatments. Further analysis revealed a negative association (r = −0.32, p < 0.01) between changes in levels of anxiety and changes in V̇O in all participates, no other correlations were found between changes in psychological and physiological parameters. Conclusion: Although the combination of a LCD and exercise may not induce additional reductions in body weight in overweight young females, exercise could be a useful add-on treatment along with a LCD to improve cardiometabolic health and lower anxiety levels.