We investigated how the complexity of fetal heart rate fluctuations (fHRF) is related to the sleep states in sheep and human fetuses. The complexity as a function of time scale for fetal heart rate data for 7 sheep and 27 human fetuses was estimated in rapid eye movement (REM) and non-REM sleep by means of permutation entropy and the associated Kullback-Leibler entropy. We found that in humans, fHRF complexity is higher in non-REM than REM sleep, whereas in sheep this relationship is reversed. To show this relation, choice of the appropriate time scale is crucial. In sheep fetuses, we found differences in the complexity of fHRF between REM and non-REM sleep only for larger time scales (above 2.5 s), whereas in human fetuses the complexity was clearly different between REM and non-REM sleep over the whole range of time scales. This may be due to inherent time scales of complexity, which reflect species-specific functions of the autonomic nervous system. Such differences have to be considered when animal data are translated to the human situation.