Estimating the extent to which newborn humans process input from their environment, especially regarding the depth of processing, is a challenging question. To approach this problem, we measured brain responses in 20 newborns with magnetoencephalography (MEG) in a “local-global” auditory oddball paradigm in which two-levels of hierarchical regularities are presented. Results suggest that infants in the first weeks of life are able to learn hierarchical rules, yet a certain level of vigilance seems to be necessary. Newborns detected violations of the first-order regularity and displayed a mismatch response between 200−400 ms. Violations of the second-order regularity only evoked a late response in newborns in an active state, which was expressed by a high heart rate variability. These findings are in line with those obtained in human adults and older infants suggesting a continuity in the functional architecture from term-birth on, despite the immaturity of the human brain at this age.