The deregulation of the autonomic nervous system assessed through the heart rate variability (HRV) analysis is a promising pathway linking work stress and cardiovascular diseases. We aim to investigate the associations between HRV High Frequency (HF) and Low Frequency (LF) powers and work stress in a sample of 36 healthy nurses. Perceived work stress was assessed twice one year apart, using the Job Content and Effort Reward Imbalance questionnaires. This allows to classify nurses in three exposure groups: "prolonged high stress" (PHS), "recent high stress" (RHS) and "stable low stress" (SLS). A 24-h ECG monitoring was later performed during a working day (WD) and a subsequent resting day (RD). Statistically significantly lower (p < 0.02) HF and LF means were found in PHS and RHS nurses during the working periods. In the subsequent resting periods, HF means showed increases over time in the RHS (beta = +0.41, p < 0.05), but not in PHS nurses. LF means did not show any substantial increases in the resting periods, in the PHS group with geometric means lower when compared to SLS, in the non-working and resting periods. Our study evidences that both prolonged and recent perceived high work stress were associated with a reduction of HF and LF powers during work. In addition, prolonged stress was associated with a lack of recovery during not-working and resting periods.