Background Very little research has been done to simultaneously investigate the effects of Tai Chi (TC) on depression and heart rate variability (HRV). This study, therefore, attempted to explore the effects of TC on depression and on HRV parameters. Methods Sixty older individuals with depression score of 10 or above (the Geriatric Depression Scale, GDS) were randomly assigned into two groups: TC (n = 30) and control group (n = 30). Participants in the experimental group participated in a 24-week TC training program (three 60-min sessions per week), whereas individuals in the control group maintained their unaltered lifestyle. Depression and HRV were measured using the GDS and digital electrocardiogram at baseline and after the 24-week intervention. Results The TC had produced significant positive chances in depression and some HRV parameters (mean heart rate, RMSSD, HF, LFnorm, and HFnorm) (p < 0.05), whereas these positive results were not observed in the control group. Conclusions The results of this study indicated that TC may alleviate depression of the elderly through modulating autonomous nervous system or HRV parameters. This study adds to a growing body of research showing that TC may be effective in treating depression of the elderly. Tai Chi as a mild to moderate mind-body exercise is suitable for older individuals who suffer from depression.