Obstructive sleep apnea (OSA) is a fatal respiratory disease occurring in sleep. OSA can induce declined heart rate variability (HRV) and was reported to have autonomic nerve system (ANS) dysfunction. Variance delay fuzzy approximate entropy (VD_fApEn) was proposed as a nonlinear index to study the fluctuation change of ANS in OSA patients. Sixty electrocardiogram (ECG) recordings of the PhysioNet database (20 normal, 14 mild-moderate OSA, and 26 severe OSA) were intercepted for 6 h and divided into 5-min segments. HRV analysis were adopted in traditional frequency domain, and nonlinear HRV indices were also calculated. Among these indices, VD_fApEn could significantly differentiate among the three groups (p < 0.05) compared with the ratio of low frequency power and high frequency power (LF/HF ratio) and fuzzy approximate entropy (fApEn). Moreover, the VD_fApEn (90%) reached a higher OSA screening accuracy compared with LF/HF ratio (80%) and fApEn (78.3%). Therefore, VD_fApEn provides a potential clinical method for ANS fluctuation analysis in OSA patients and OSA severity analysis.