Obstructive sleep apnea (OSA) is a serious sleep disorder, which leads to changes in autonomic nerve function and increases the risk of cardiovascular disease. Heart rate variability (HRV) has been widely used as a non-invasive method for assessing the autonomic nervous system (ANS). We proposed the two-dimensional sample entropy of the coarse-grained Gramian angular summation field image (CgSampEn(2D)) index. It is a new index for HRV analysis based on the temporal dependency complexity. In this study, we used 60 electrocardiogram (ECG) records from the Apnea-ECG database of PhysioNet (20 healthy records and 40 OSA records). These records were divided into 5-min segments. Compared with the classical indices low-to-high frequency power ratio (LF/HF) and sample entropy (SampEn), CgSampEn(2D) utilizes the correlation information between different time intervals in the RR sequences and preserves the temporal dependency of the RR sequences, which improves the OSA detection performance significantly. The OSA screening accuracy of CgSampEn(2D) (93.3%) is higher than that of LF/HF (80.0%) and SampEn (73.3%). Additionally, CgSampEn(2D) has a significant association with the apnea-hypopnea index (AHI) (R = -0.740, p = 0). CgSampEn(2D) reflects the complexity of the OSA autonomic nerve more comprehensively and provides a novel idea for the screening of OSA disease.