Purpose: The prognostic power of heart rate recovery (HRR) after exercise has been well established but the exact origin of individual differences in HRR remains unclear. This study aims to estimate the heritability of HRR and vagal rebound after maximal exercise in adolescents. Furthermore, the role of voluntary regular exercise behavior (EB) in HRR and vagal rebound is tested. Methods: 491 healthy adolescent twins and their siblings were recruited for maximal exercise testing, followed by a standardized cooldown with measurement of the electrocardiogram and respiratory frequency. Immediate and long-term HRR (HRR60 and HRR180) and vagal rebound (heart rate variability in the respiratory frequency range) were assessed 1 and 3 min after exercise. Multivariate twin modeling was used to estimate heritability of all measured variables and to compute the genetic contribution to their covariance. Results: Heritability of HRR60, HRR180 and immediate and long-term vagal rebound is 60 % (95 % CI: 48–67), 65 % (95 % CI: 54–73), 23 % (95 % CI: 11–35) and 3 % (95 % CI: 0–11), respectively. We find evidence for two separate genetic factors with one factor influencing overall cardiac vagal control, including resting heart rate and respiratory sinus arrhythmia, and a specific factor for cardiac vagal exercise recovery. EB was only modestly associated with resting heart rate (r = −0.27) and HRR (rHRR60 = 0.10; rHRR180 = 0.19) with very high genetic contribution to these associations (88–91 %). Conclusions: Individual differences in HRR and immediate vagal rebound can to a large extent be explained by genetic factors. These innate cardiac vagal exercise recovery factors partly reflect the effects of heritable differences in EB.