Previous studies demonstrated that increases in the theta frequency band with concomitant decreases in the alpha/beta frequency band indicate successful memory formation. However, little is known about the brain regions and the cognitive processes that underlie these encoding-related oscillatory memory effects. We investigated this relationship using simultaneous EEG-fMRI recordings in humans during long-term memory encoding. In line with prior studies, we demonstrate that a decrease in beta power and an increase in theta power positively predict subsequent recall. In fMRI, stronger activity in the left inferior prefrontal cortex and the right parahippocampal gyrus correlated with successful memory formation. EEG source localization revealed that the subsequent memory effect in the beta band was localized in the left inferior prefrontal cortex, whereas the effect in the theta band was localized in medial temporal lobe regions. Trial-by-trial correlations between EEG and BOLD activity showed that beta power correlated negatively with left inferior prefrontal cortex activity. This correlation was more pronounced for items that could later be successfully recalled compared to items later forgotten. Based on these findings, we suggest that beta oscillations in the left inferior prefrontal cortex indicate semantic encoding processes, whereas theta oscillations in the medial temporal lobe reflect the binding of an item to its spatiotemporal context.