Evidence suggests that exposure to psychosocial stress at work can inhibit vagal tonus, influencing the capacity to respond to environmental stimuli. We investigated whether job strain and low control and high demand at work, as separate measures, are associated with a reduction in heart rate variability (HRV). Methods: This is a cross-sectional study with 9658 active workers at the baseline (2008–2010) of the Brazilian Longitudinal Study of Adult Health (ELSA–Brasil). HRV was estimated using electrocardiographic recordings for 10 minutes, at rest, examining the following indices were used: root mean square of successive difference, standard deviation of normal to normal, percentage of adjacent R-R intervals with a difference lasting more than 50 ms, low frequency (LF), and high frequency. Job strain was defined based on the demand-control model. Independent associations between job strain and HRV indices were verified using generalized linear models and the magnitude of the association was estimated by evaluating the ratios of arithmetic means. Results: Neither the unfavorable demand-control relation nor job demand dimension separately was associated with HRV. However, the increase of one unit in the control dimension was associated with an increment of 2.2% (95% confidence interval = 1.014–1.029) in the LF mean. After adjustments for sociodemographic characteristics, assessment site, health-related behaviors, and depression, this association remained statistically significant (ratio of arithmetic means = 1.008; 95% confidence interval = 1.0002–1.017). Conclusions: Job control was associated with HRV in a large cohort of civil servants. Nevertheless, it is important to emphasize that only the LF index remained associated with low job control. Further studies are needed to develop a greater understanding of the relationship of psychosocial aspects and autonomic balance.