The purpose of this study was to evaluate differences in heart rate recovery (HRr) in trained and untrained adults, while assessing the role of physiological and emotional factors. Eighteen untrained and 21 trained participants completed a maximal exercise test and a 20-min treadmill exercise at 55–70% heart rate reserve, and emotional state was assessed prior to exercise. Multiple regression was used to assess relationships between heart rate recovery and physiological and emotional assessments. The trained group had a higher relative maximal oxygen consumption (p < 0.001), lower resting heart rate (p < 0.001), and faster short- and long-term heart rate recovery (p < 0.05) than the untrained group. Resting heart rate was the most predictive measure with HRr for the trained group (R = 0.551–0.818), whereas resting heart rate, maximal heart rate, and fitness were predictors of recovery in the untrained group (R = 0.764–0.977). The results show the predominant parasympathetic influence on HRr in the trained group, but indicates influence of fitness and exercise intensity on recovery in the untrained group. Thus, fitness appears to influence HRr in those only with low fitness. This notion may help influence the behavior of untrained individuals to improve fitness to reduce risk of mortality and morbidity.