Human episodic memory is highly context dependent. Therefore, retrieval benefits when a memory is recalled in the same context compared to a different context. This implies that items and contexts are bound together during encoding, such that the reinstatement of the initial context at test improves retrieval. Animal studies suggest that theta oscillations and theta-to-gamma cross-frequency coupling modulate such item-context binding, but direct evidence from humans is scarce. We investigated this issue by manipulating the overlap of contextual features between encoding and retrieval. Participants studied words superimposed on movie clips and were later tested by presenting the word with either the same or a different movie. The results show that memory performance and the oscillatory correlates of memory formation crucially depend on the overlap of the context between encoding and test. When the context matched, high theta power during encoding was related to successful recognition, whereas the opposite pattern emerged in the context-mismatch condition. In addition, cross-frequency coupling analysis revealed a context-dependent theta-to-gamma memory effect specifically in the left hippocampus. These results reveal for the first time that context-dependent episodic memory effects are mediated by theta oscillatory activity.