Associative learning requires mapping between complex stimuli and behavioural responses. When multiple stimuli are involved, conditional associative learning is a gradual process with learning based on trial and error. It is established that a distributed network of regions track associative learning, however the role of neural oscillations in human learning remains less clear. Here we used scalp EEG to test how neural oscillations change during learning of arbitrary visuo-motor associations. Participants learned to associative 48 different abstract shapes to one of four button responses through trial and error over repetitions of the shapes. To quantify how well the associations were learned for each trial, we used a state-space computational model of learning that provided a probability of each trial being correct given past performance for that stimulus, that we take as a measure of the strength of the association. We used linear modelling to relate single-trial neural oscillations to single-trial measures of association strength. We found frontal midline theta oscillations during the delay period tracked learning, where theta activity was strongest during the early stages of learning and declined as the associations were formed. Further, posterior alpha and low-beta oscillations in the cue period showed strong desynchronised activity early in learning, while stronger alpha activity during the delay period was seen as associations became well learned. Moreover, the magnitude of these effects during early learning, before the associations were learned, related to improvements in memory seen on the next presentation of the stimulus. The current study provides clear evidence that frontal theta and posterior alpha/beta oscillations play a key role during associative memory formation.