Sleep’s ubiquitous presence across the animal kingdom underscores its crucial role in an organism’s cognitive, emotional, and physiological function. In mammals, sleep is subdivided into two distinct substates: Rapid Eye Movement (REM) sleep and Non-rapid Eye Movement (NREM) sleep. NREM sleep is marked by synchronized brain activity and muscle tone loss, while REM sleep is characterized by desynchronized brain activity, muscle atonia, and bursts of eye movements. Nevertheless, the definition of sleep varies across species making the evolutionary origin of distinct sleep states unclear. In organisms like C. elegans, Drosophila, and zebrafish, sleep is defined as periods of locomotor quiescence (>= 1 min) with heightened arousal thresholds. Using longitudinal, high-resolution imaging of naturalistic sleep-wake behavior, we find that the classical definition of larval zebrafish sleep in fact encompasses two clearly distinct states, one with rapid eye movements (qREM) and one without rapid eye movements (qNREM). Using brain-wide imaging in freely swimming larval zebrafish, we confirmed that brain activity, including the noradrenergic cells of the locus coeruleus, is broadly suppressed during qREM, consistent with it being a sleep-like state. In contrast to the previously established fixed point attractor model of sleep in C. elegans, selected neuronal subpopulations in larval zebrafish remain active during qREM and evolve along organized, committed trajectories through the state-space of population activity, raising the possibility that distinct neural dynamics emerged in the evolution of vertebrate sleep. This work illuminates the evolutionary origin and function of REM sleep.