Sleep diseases, such as insomnia and obstructive sleep apnea, seriously affect patients’ quality of life. For diagnosis, polysomnographic (PSG) recordings are most usually taken to evaluate the sleep quality and efficiency. However, the large amount of wires connections for conventional PSG often cause sleep interference and not self-applicable. In this study, a complexity-measure-based method for evaluating the sleep quality was proposed. We utilize multiscale entropy (MSE) to analyze the 32 all-night sleep polysomnographic (PSG) recordings from 32 adults. The range of the subjects’ sleep efficiency was from 56% to 97%. Half of the subjects’ sleep efficiencies were equal or higher than to 85% (good sleep) and the other half were lower than 85% (poor sleep). The result shows that the averaged MSE values of poor sleep efficiency group are higher than good sleep efficiency group in each scale factor. This means that the complexity of sleep EEG of poor sleep efficiency group is higher than good sleep efficiency group. This finding may be used to quickly distinguish the subject’ sleep efficiency is good or poor.