In this paper, a new algorithm is proposed for artifact removing of sleep electroencephalogram (EEG) with application in sleep stage classification. Rather than other works which used artificial noise, in this study real EEG data contaminated with electro-oculogram (EOG) and electromyogram (EMG) are used for evaluating the proposed artifact removal algorithm’s efficiency using classification accuracy. The artifact detection is performed by thresholding the EEG-EOG and EEG-EMG cross correlation coefficients. Then, the segments considered contaminated are denoised by normalized least-mean squares (NLMS) adaptive filtering technique. Using a single EEG channel, four sleep stages consisting of Awake, Stage1 + REM, Stage 2 and Slow Wave Stage (SWS) are classified. A wavelet packet (WP) based feature set together with artificial neural network (ANN) are deployed for sleep stage classification purpose. Simulation results show that artifact removed EEG allows a classification accuracy improvement of around 14 %.