Background/Objectives: Teaching is a profession characterized by a high burden of stress. This study examined sex differences in autonomic regulation by analysing heart rate variability (HRV) and body fat percentage (BF%) in teachers, explicitly hypothesizing that the association between adiposity and autonomic modulation (HRV) would be more consistent in men. Methods: A cross-sectional study was conducted with 253 teachers from compulsory and university education during the 2022–2023 academic year. HRV was obtained from heart rate recordings, and body composition was assessed using bioelectrical impedance analysis. Analyses were stratified by sex and, in addition to comparisons based on the sex-specific median of fat mass (kg), ANCOVA models were performed and adjusted for age, teaching experience, and educational level. Results: Teachers with higher BF% were older (43.46 vs. 40.65 years; p = 0.007) and reported higher perceived stress (7.60 vs. 6.83; p = 0.034). In men, HRV was lower in the ≥p50 adiposity group, with reductions in RMSSD and pNN50 (p = 0.015–0.016). In women, RMSSD and pNN50 were not significant (p > 0.20; small effect sizes). In adjusted analyses (ANCOVA), no significant differences were found in men for any index; in women, HRmax and the LF/HF ratio were significant (small effects), whereas the remaining indices were not. Conclusions: Greater adiposity was associated with higher stress and lower HRV, particularly in men. In women, the pattern was more heterogeneous, and significance after adjustment was limited to HRmax and the LF/HF ratio, suggesting the need for sex-specific approaches to the assessment and promotion of psychophysiological well-being in teachers.