Early studies of the echidna led to the conclusion that this monotreme did not have rapid eye movement (REM) sleep. Because the monotremes had diverged from the placental and marsupial lines very early in mammalian evolution, this finding was used to support the hypothesis that REM sleep evolved after the start of the mammalian line. The current paper summarizes our recent work on sleep in the echidna and platypus and leads to a very different interpretation. By using neuronal recording from mesopontine regions in the echidna, we found that despite the presence of a high-voltage cortical electroencephalogram (EEG), brainstem units fire in irregular bursts intermediate in intensity between the regular non-REM sleep pattern and the highly irregular REM sleep pattern seen in placentals. Thus the echidna displays brainstem activation during sleep with high-voltage cortical EEG. This work encouraged us to do the first study of sleep, to our knowledge, in the platypus. In the platypus we saw sleep with vigorous rapid eye, bill and head twitching, identical in behaviour to that which defines REM sleep in placental mammals. Recording of the EEG in the platypus during natural sleep and waking states revealed that it had moderate and high-voltage cortical EEGs during this REM sleep state. The platypus not only has REM sleep, but it had more of it than any other animal. The lack of EEG voltage reduction during REM sleep in the platypus, and during the REM sleep-like state of the echidna, has some similarity to the sleep seen in neonatal sleep in placentals. The very high amounts of REM sleep seen in the platypus also fit with the increased REM sleep duration seen in altricial mammals. Our findings suggest that REM sleep originated earlier in mammalian evolution than had previously been thought and is consistent with the hypothesis that REM sleep, or a precursor state with aspects of REM sleep, may have had its origin in reptilian species.