This study investigated the effects of moderate-intensity exercise on reducing stress and depression and improving self-esteem of women in early adulthood. The Korean version of the Perceived Stress Scale (K-PSS) was administered to 60 non-clinical women aged 19-40, and 36 women with relatively high stress finally selected. They were randomly assigned to a moderate-intensity exercise group, a low-intensity walking group, and a control group with 12 participants in each group. Moderate-intensity exercise group showed significant reductions in stress at mid- and post-intervention, as well as decreases in depression and improvements in self-esteem at post-intervention. The effects of all variables were maintained at follow-up. Walking Group demonstrated significant reductions in stress at post-intervention and follow-up, but no significant differences in depression and self-esteem. The control group showed no significant changes in stress (pre-, post-, follow-up) or in depression and self-esteem (pre-, mid-, post-, follow-up). Limitations and directions for future research were discussed.