Frontal-midline (fm) theta oscillations as measured via the electroencephalogram (EEG) have been suggested as neural "working language" of executive functioning. Their power has been shown to increase when cognitive processing or task performance is enhanced. Thus, the question arises whether learning to increase fm-theta amplitudes would functionally impact the behavioral performance in tasks probing executive functions (EFs). Here, the effects of neurofeedback (NF), a learning method to self-up-regulate fm-theta over fm electrodes, on the four most representative EFs, memory updating, set shifting, conflict monitoring, and motor inhibition are presented. Before beginning and after completing an individualized, eight-session gap-spaced NF intervention, the three-back, letter/number task-switching, Stroop, and stop-signal tasks were tested while measuring the EEG. Self-determined up-regulation of fm-theta and its putative role for executive functioning were compared to an active control group, the so-called pseudo-neurofeedback group. Task-related fm-theta activity after training differed significantly between groups. More importantly, though, after NF significantly enhanced behavioral performance was observed. The training group showed higher accuracy scores in the three-back task and reduced mixing and shifting costs in letter/number task-switching. However, this specific protocol type did not affect performance in tasks probing conflict monitoring and motor inhibition. Thus, our results suggest a modulation of proactive but not reactive mechanisms of cognitive control. Furthermore, task-related EEG changes show a distinct pattern for fm-theta after training between the NF and the pseudo-neurofeedback group, which indicates that NF training indeed tackles EFs-networks. In sum, the modulation of fm-theta via NF may serve as potent treatment approach for executive dysfunctions.