An effective physiological pain assessment method that complements the gold standard of self-report is highly desired in pain clinical research and practice. Recent studies have shown that pain-evoked electroencephalography (EEG) responses could be used as a readout of perceived pain intensity. Existing EEG-based pain assessment is normally achieved by cross-individual prediction (i.e., to train a prediction model from a group of individuals and to apply the model on a new individual), so its performance is seriously hampered by the substantial inter-individual variability in pain-evoked EEG responses. In this study, to reduce the inter-individual variability in pain-evoked EEG and to improve the accuracy of cross-individual pain prediction, we examined the relationship between pain-evoked EEG, spontaneous EEG, and pain perception on a pain EEG dataset, where a large number of laser pulses (>100) with a wide energy range were delivered. Motivated by our finding that an individual’s pain-evoked EEG responses is significantly correlated with his/her spontaneous EEG in terms of magnitude, we proposed a normalization method for pain-evoked EEG responses using one’s spontaneous EEG to reduce the inter-individual variability. In addition, a nonlinear relationship between the level of pain perception and pain-evoked EEG responses was obtained, which inspired us to further develop a new two-stage pain prediction strategy, a binary classification of low-pain and high-pain trials followed by a continuous prediction for high-pain trials only, both of which used spontaneous-EEG-normalized magnitudes of evoked EEG responses as features. Results show that the proposed normalization strategy can effectively reduce the inter-individual variability in pain-evoked responses, and the two-stage pain prediction method can lead to a higher prediction accuracy.