The risk of dementia increases with age. To mitigate this risk, we examined the effect of a square-stepping exercise (SSE) program on fall-related fitness and brain-derived neurotrophic factor (BDNF) levels. Twenty older adults in Korea were randomly assigned to either the experimental or control group (each group n = 10). Participants performed SSE for 70 min per session, twice a week, for 12 weeks with a certified instructor. The average age of the participants was 74.80 ± 6.763 years in the exercise group and 72.50 ± 6.519 years in the control group. The experiment group showed significant improvement (p < 0.01) in the lower muscle strength post-intervention. The paired t-test revealed a significant improvement (p < 0.01) in the experimental group and a significant difference in the interaction effect (p < 0.01) in the BDNF levels. There was a significant improvement (p < 0.05) in the BDNF levels in the experimental group and a significant decrease (p < 0.05) in the control group. The SSE program had a positive effect on fall-related fitness and BDNF levels.