Rapid eye movement (REM) sleep or paradoxical sleep is an elusive behavioral state. Since its discovery in the 1950s, our knowledge of the neuroanatomy, neurotransmitters and neuropeptides underlying REM sleep regulation has continually evolved in parallel with the development of novel technologies. Although the pons was initially discovered to be responsible for REM sleep, it has since been revealed that many components in the hypothalamus, midbrain, pons, and medulla also contribute to REM sleep. In this review, we first provide an up-to-date overview of REM sleep-regulating circuits in the brainstem and hypothalamus by summarizing experimental evidence from neuroanatomical, neurophysiological and gain- and loss-of-function studies. Second, because quantitative approaches are essential for understanding the complexity of REM sleep-regulating circuits and because mathematical models have provided valuable insights into the dynamics underlying REM sleep genesis and maintenance, we summarize computational studies of the sleep-wake cycle, with an emphasis on REM sleep regulation. Finally, we discuss outstanding issues for future studies.