Sequence memory is subject to age-related decline, but the underlying processes are not yet fully understood. We analyzed electroencephalography (EEG) in 21 healthy older (60–80 years) and 26 young participants (20–30 years) and compared time-frequency spectra and theta-gamma phase-amplitude-coupling (PAC) during encoding of the order of visually presented items. In older adults, desynchronization in theta (4–8 Hz) and synchronization in gamma (30–45 Hz) power did not distinguish between subsequently correctly and incorrectly remembered trials, while there was a subsequent memory effect for young adults. Theta-gamma PAC was modulated by item position within a sequence for older but not young adults. Specifically, position within a sequence was coded by higher gamma amplitude for successive theta phases for later correctly remembered trials. Thus, deficient differentiation in theta desynchronization and gamma oscillations during sequence encoding in older adults may reflect neurophysiological correlates of age-related memory decline. Furthermore, our results indicate that sequences are coded by theta-gamma PAC in older adults, but that this mechanism might lose precision in aging.