To assess maturation of the Autonomic Nervous System (ANS) and sleep states, Heart Rate Variability (HRV) was studied in 24 healthy sleeping newborns, aged from 31 to 41 weeks, conceptional age (CA). Spectral analysis of the interbeat interval (RR) signal, was performed by Short-Time Fourier Transform, in three frequency bands: high (HF), of purely vagal origin, mid (MF), and low (LF), vagal and sympathetic, thus allowing evaluation of both branches of the ANS, observed in Active Sleep (AS = REM Sleep) and in Quiet Sleep (QS = nREM Sleep). Principal Component Analysis, Discriminant Analysis, and hypothesis tests were used to investigate the evolution of spectral variables and their relation with sleep states. HF, MF, LF, and mean RR all increased with age; the differences from the premature to the full-term group, were more marked, as a whole, in AS than in QS. HF showed the highest increase from the premature (31-36 weeks CA) to the intermediate (37-38) group, whereas LF showed equal differences from the premature to the intermediate, and from the intermediate to the full-term (39-41) groups. These results suggest a steep increase in vagal tone at 37-38 weeks CA, with stability afterwards, and a more regular increase in sympathetic tone from 31 to 41 weeks CA.