Task-related power changes in the EEG alpha band were analyzed in 31 participants (17 males and 14 females) during performance of two verbal creativity tasks. Participants were confronted with verbal problems that are in need of explanation (insight problems) and utopian situations that will actually never happen. In both tasks they were instructed to generate as many but also as unusual, unique or original ideas as possible. To assess brain responses that come along with highly original ideas, individual responses were divided into more and less original ideas (within each participant). Creative problem solving was generally accompanied by lower levels of cortical arousal (i.e., increases in alpha power from a pre-stimulus reference to an activation interval). Additionally, more original (vs. less original) responses were associated with a stronger task-related alpha synchronization in posterior (particularly centroparietal) cortices. Task-related alpha power changes during creative problem solving were also moderated by verbal IQ and sex.