Obstructive sleep apnea (OSA) is an independent cardiovascular risk factor to which autonomic nervous dysfunction has been reported to be an important contributor. Ninety subjects recruited from the sleep center of a single medical center were divided into four groups: normal snoring subjects without OSA (apnea hypopnea index, AHI < 5, n = 11), mild OSA (5 ≤ AHI < 15, n = 10), moderate OSA (15 ≤ AHI < 30, n = 24), and severe OSA (AHI ≥ 30, n = 45). Demographic (i.e., age, gender), anthropometric (i.e., body mass index, neck circumference), and polysomnographic (PSG) data were recorded and compared among the different groups. For each subject, R-R intervals (RRI) from 10 segments of 10-minute electrocardiogram recordings during non-rapid eye movement sleep at stage N2 were acquired and analyzed for heart rate variability (HRV) and sample entropy using multiscale entropy index (MEI) that was divided into small scale (MEI_SS, scale 1–5) and large scale (MEI_LS, scale 6–10). Our results not only demonstrated that MEI_SS could successfully distinguish normal snoring subjects and those with mild OSA from those with moderate and severe disease, but also revealed good correlation between MEI_SS and AHI with Spearman correlation analysis (r = −0.684, p < 0.001). Therefore, using the two parameters of EEG and ECG, MEI_SS may serve as a simple preliminary screening tool for assessing the severity of OSA before proceeding to PSG analysis.