We aimed to investigate the effects of aerobic exercise on pain perception, sensitivity, and health-related quality of life; to assess its effect on parasympathetic tonus by analysis of heart rate recovery; and to examine the effects of parasympathetic tone on pain sensitivity in patients with chronic musculoskeletal pain. Fifty patients with chronic musculoskeletal pain were randomized into two groups: control group (C group) and aerobic exercise group (AE group). Both groups received conventional physical therapy for 2 weeks; the AE group performed submaximal aerobic exercise on a treadmill for 30 min additionally. Exercise test, pressure-pain threshold measurement, short form-36, and visual analog scale were administered initially and finally for evaluation. Visual analog scale scores in both groups decreased significantly after treatment (P<0.001). Pressure-pain threshold sum increased significantly in the AE group, remaining unchanged in the C group. Increase in exercise test duration was significant in the AE group compared with the C group (P=0.0002). Heart rate recovery did not change with therapy in the groups. For short form-36, the AE group showed alterations in role limitations because of physical problems and general health perceptions; both groups showed a significant improvement in the physical function and bodily pain subscales, but mental health significantly improved only in C group. Short-term aerobic exercise along with conventional physical therapy decreased pain sensitivity and increased aerobic capacity, with significant improvements in health-related quality of life.