Theta phase modulates gamma amplitude during spatial navigation and rapid eye movement sleep (REMs). Although the REMs theta rhythm has been linked to spatial memory consolidation, the underlying mechanism remains unclear. We investigate dynamics of theta-gamma interactions across multiple frequency and temporal scales in simultaneous recordings from hippocampal CA3, CA1, subiculum, and parietal cortex. We show that theta phase significantly modulates three distinct gamma bands during REMs, dynamically. Interestingly, we further show that theta-gamma coupling swings between different hippocampal and cortical structures during REMs and tends to increase over a single REMs episode. Comparing to active wake, theta-gamma coupling during REMs is significantly increased for subicular and cortical, but not for CA3 and CA1, recordings. Finally, optogenetic silencing of septohippocampal GABAergic projections significantly impedes both theta-gamma coupling and theta phase coherence, two neural mechanisms of working and long-term memory, respectively. Thus, we show that theta-gamma coupling and theta phase coherence are highly modulated during single REMs episode and propose that theta-gamma coupling provides a predominant mechanism for information processing within each brain region, while the orchestrated nature of coupling activity establishes a specific phase-space coding of information during sleep.