Newborn infants must rapidly adjust their physiology and behavior to the specific demands of the novel postnatal environment. This adaptation depends, at least in part, on the infant’s ability to learn from experiences. We report here that infants exhibit learning even while asleep. Bioelectrical activity from face and scalp electrodes was recorded from neonates during an eye movement conditioning procedure in which a tone was followed by a puff of air to the eye. Sleeping newborns rapidly learned the predictive relationship between the tone and the puff. Additionally, in the latter part of training, these infants exhibited a frontally maximum positive EEG slow wave possibly reflecting memory updating. As newborns spend most of their time sleeping, the ability to learn about external stimuli in the postnatal environment during nonawake states may be crucial for rapid adaptation and infant survival. Furthermore, because eyelid conditioning reflects functional cerebellar circuitry, this method potentially offers a unique approach for early identification of infants at risk for a range of developmental disorders including autism and dyslexia.