Paired-associates learning of unrelated words can reflect the formation of a new association in the semantic network. Research results on the facilitating effect of sleep on unrelated word-pair associates learning remain contradictory. The behavioral measures used in previous studies may not have been sensitive enough to reflect the process of new word association during sleep. The present study used the N400 component of event-related potential (ERP) to further assess the facilitating effect of sleep on the formation of new semantic associations. Thirty subjects were randomly assigned to either the Sleep group or the Wakefulness group. After paired-associates learning and pre-test, they underwent nocturnal sleep and sleep deprivation, respectively. A post-test was conducted after the subjects had one night of recovery sleep. ERPs were recorded during both test phases. Behavioral data showed significant differences in improvements in recognition and decreases in reaction time from pre-test to post-test between the Sleep and Wakefulness groups. The N400 peak amplitude attenuated significantly after sleep, but not after wakefulness. These results suggest that sleep has a facilitating effect on the formation of novel associations. Unexpectedly, slow wave sleep was negatively correlated with improvement in recognition during the post-test but was positively correlated with the number of word-pairs acquired during the learning phase. This may the result of a ceiling effect limiting the improvement achieved in subjects who learned better during the learning phase.