This study assessed the effectiveness of an 8-week aerobic exercise program on heart rate variability (HRV) in people living with HIV taking antiretroviral therapy. Twenty-six participants were randomly assigned to a control group or an aerobic exercise group. Resting HRV was measured for 5 min in supine position using an electrocardiogram. Estimated maximal oxygen uptake (VO(2max)) was assessed through a treadmill 6-min walk test. The training program consisted of aerobic exercise thrice per week at 65%-75% of heart rate max for 45 min per session. Repeated measures ANOVA was used to test for differences between groups, and Spearman\'s rho was used to assess for the correlation between HRV measures and estimated VO(2max). There was no significant group by time interactions for any of the HRV indices. However, the standard deviation of normal-to-normal (NN) R-R intervals increased significantly in the aerobic exercise group (pre: 46.97 +/- 32.70 ms vs. post: 59.49 +/- 37.20 ms, p = .045). There was a strong correlation between the VO(2max) and the standard deviation of NN intervals (SDNN) (r = 0.617; p = .002). There was a moderate correlation between VO(2max) and the square root of the mean squared differences of successive normal-to-normal intervals (rMSSD) (r = 0.424; p = .049), the low frequency power (r = 0.506; p = .016), and the standard deviation of differences between successive differences of normal-to-normal intervals (SDSD) (r = 0.424; p = .049). While differences in HRV were not observed between groups, our data suggest that overall autonomic function can improve across time with aerobic exercise, and these changes are associated with greater levels of VO(2max). These results advocate the importance of improvements in HRV given their association with lower risk of cardiovascular disease and mortality.