Established sleep cycling is one of the main hallmarks of early brain development in preterm infants, therefore, automated classification of the sleep stages in preterm infants can be used to assess the neonate’s cerebral maturation. Tensor algebra is a powerful tool to analyze multidimensional data and has proven successful in many applications. In this paper, a novel unsupervised algorithm to identify neonatal sleep stages based on the decomposition of a multiscale entropy tensor is presented. The method relies on the difference in electroencephalography(EEG) complexity between the neonatal sleep stages and is evaluated on a dataset of 97 EEG recordings. An average sensitivity, specificity, accuracy and area under the receiver operating characteristic curve of 0.80, 0.79, 0.79 and 0.87 was obtained if the rank of the tensor decomposition is selected based on the age of the infant.