Most studies have investigated brain activation changes after the course of arithmetic learning, and the question remains whether these changes are detectable during the course of learning, i.e., before memory consolidation. Twenty-four fifth graders solved multiplication problems while ongoing electroencephalography (EEG) was recorded. The arithmetic training revealed reduced errors together with a power increase in theta (4-7 Hz) but not in lower alpha (8-10 Hz) or upper alpha (10-13 Hz) bands. We conclude that increases in theta power subserved a shift from slow, procedural strategies to more efficient, automated procedural and retrieval strategies, which led to more efficient performance.