When subjects are given the balls-and-boxes problem-solving task (Kotovsky & Simon, 1990), they move rapidly towards the goal after an extended exploratory phase, despite having no awareness of how to solve the task. We investigated possible non-conscious learning mechanisms by giving subjects three runs of the task while recording ERPs. Subjects showed significant differences in their ERP components during the exploratory phase between correct and incorrect moves. Exploratory incorrect moves were associated with a shallower response-locked N1 component and a larger response-locked P3 component compared with exploratory correct moves. Subjects who solved the task more quickly exhibited a trend towards larger N1 and P3 components. These results suggest that the brain processes information about the correctness of a move well before subjects are aware of move correctness. They further suggest that relatively simple attentional and error-monitoring processes play an important role in complex problem-solving.